2014
04-09

# Monkey Party

Far away from our world, there is a banana forest. And many lovely monkeys live there. One day, SDH(Song Da Hou), who is the king of banana forest, decides to hold a big party to celebrate Crazy Bananas Day. But the little monkeys don’t know each other, so as the king, SDH must do something.
Now there are n monkeys sitting in a circle, and each monkey has a making friends time. Also, each monkey has two neighbor. SDH wants to introduce them to each other, and the rules are:
1.every time, he can only introduce one monkey and one of this monkey’s neighbor.
2.if he introduce A and B, then every monkey A already knows will know every monkey B already knows, and the total time for this introducing is the sum of the making friends time of all the monkeys A and B already knows;
3.each little monkey knows himself;
In order to begin the party and eat bananas as soon as possible, SDH want to know the mininal time he needs on introducing.

There is several test cases. In each case, the first line is n(1 ≤ n ≤ 1000), which is the number of monkeys. The next line contains n positive integers(less than 1000), means the making friends time(in order, the first one and the last one are neighbors). The input is end of file.

There is several test cases. In each case, the first line is n(1 ≤ n ≤ 1000), which is the number of monkeys. The next line contains n positive integers(less than 1000), means the making friends time(in order, the first one and the last one are neighbors). The input is end of file.

8
5 2 4 7 6 1 3 9

105

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxx=2002;

int dp[maxx][maxx],mark[maxx][maxx],sum[maxx][maxx];
//dp[i][j]表示第i个猴子到第j个猴子认识的总代价
//mark[i][j]标示最小分割点处的k值  用于四边形加速
//sum[i][j]i到j花费总和
int data[maxx];

int min(int a,int b){
return a<b?a:b;
}

int main()
{
int n;
while (scanf("%d",&n)!=EOF)
{
for (int i=1;i<=n;i++)
{
scanf("%d",&data[i]);
data[i+n]=data[i];
}
memset(sum,0,sizeof(sum));
for (int i=1;i<2*n;i++)
{
dp[i][i]=0;
mark[i][i]=i;
for (int j=i;j<=n+i;j++)
{
sum[i][j]=sum[i][j-1]+data[j];
}
}
for (int st=2;st<=n;st++)
{
for (int i=1;i+st<=2*n+1;i++)
{
int j=i+st-1;
dp[i][j]=99999999;
for (int k=mark[i][j-1];k<=mark[i+1][j];k++)
{
int temp=dp[i][k]+dp[k+1][j]+sum[i][j];
if (dp[i][j]>temp)
{
dp[i][j]=temp;
mark[i][j]=k;
}
}
}
}
int ans=9999999;
for (int i=1;i<=n;i++)
{
ans=min(ans,dp[i][i+n-1]);
}
printf("%d\n",ans);
}
return 0;
}


1. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。

2. 有一点问题。。后面动态规划的程序中
int dp[n+1][W+1];
会报错 提示表达式必须含有常量值。该怎么修改呢。。

3. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识，这句话用《爱屋及乌》描述比较容易理解……