Monkey Party hdu 3506

题目类型：动态规划，属于区间性质的，可以利用四边形不等式加速。

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3506

题目大意：一群猴子围成圈，每个猴子互相不认识，猴王要给大家互相认识，每个猴子认识别人需要一个时间花费，而且A猴子认识B猴子，则A猴子认识的所有猴子和B猴子认识的所有猴子都能认识，这个代价为所有AB猴子认识的猴子的时间花费和。 说的很绕，可以读下题，题目意思就是这样的。

思路：运用动态规划，枚举每个区间的分割点，从而找到最小花费。因为题目中给出的是环，解决的方法就是设一个长度为2*n的数组可以将环转化为线性。

转移方程：dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[i][j] i<k<j)

代码：

#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;
}