【题解】Monkey Party (HDU3506) -boshi

题意：给定一圈石子，将相邻的两堆石子合并，花费为合并后的石子数。给定一开始每一堆石子的个数，求合并的最小花费。(石子堆数<=1000)

分析：

由于是一圈石子，所以我们将其倍增以消除环的影响，然后很自然可以得出状态转移方程：设 f(i,j) 表示从 i 到 j 的石子合并的最小花费，sum[i][j] 表示从 i 到 j 的石子共有多少个 (程序中用前缀和)。
$$
f(i,j)=min(f(i,k)+f(k+1,j)+sum[i][j])
$$
但是这是 O(n³) 的算法。所以我们需要优化。
注意到 sum[i][j] 满足四边形关系，包含单调关系，所以 f 一定满足四边形不等式。由此，我们再用一个数组 s[i][j] 表示区间 f[i,j] 是通过 k=s[i][j] 使得 f[i][j] 最小的，那么状态转移方程可以变为：

$$
f(i,j)=min(f(i,k)+f(k+1,j)+sum[i][j]),s[i][j-1]\leq k\leq s[i+1][j]
$$

#include <cstdio>
#include <cstring>
using namespace std;
#define MX 2002
#define min(a,b) a<b?a:b
int a[MX],n,f[MX][MX],s[MX][MX],sum[MX];
int main()
{
    while(~scanf("%d",&n))
    {
        memset(f,0x4f,sizeof(f));
        for(int i=1;i<=n;++i)scanf("%d",&a[i]),a[n+i]=a[i];
        for(int i=1;i<=n<<1;++i)sum[i]=sum[i-1]+a[i];
        for(int i=1;i<=n<<1;++i)s[i][i]=i,f[i][i]=0;
        for(int l=1;l<=n;++l)
            for(int i=1;i+l<=n*2;++i)
                for(int k=s[i][i+l-1],j=i+l;k<=s[i+1][j];++k)
                    if(f[i][k]+f[k+1][j]+sum[j]-sum[i-1]<f[i][j])
                        f[i][j]=f[i][k]+f[k+1][j]+sum[j]-sum[i-1],s[i][j]=k;
        int mx=1<<30;
        for(int i=1;i<=n+1;++i)mx=min(mx,f[i][i+n-1]);
        printf("%d\n",mx);
    }
    return 0;
}