石子合并（一）

石子合并（一）

31 2 3713 7 8 16 21 4 18样例输出
9
239
还是有些迷迷糊糊，师兄说还可以用四边形不等式优化，还不会，以后再补充。
#include <iostream>#include <cstdio>#define INF 100000000#define N 205using namespace std;int main(){    int n,i,j;    int a[N],sum[N],dp[N][N];    while(~scanf("%d",&n)&&n)    {        sum[0]=0;        for(i=1;i<=n;i++)        {            scanf("%d",&a[i]);            dp[i][i]=0;            sum[i]=sum[i-1]+a[i];        }        //题目要求是相邻的        for(int l=2;l<=n;l++)//2,3,4堆合并        {            for(i=1;i<=n-1+1;i++)            {                j=i+l-1;                dp[i][j]=INF;                for(int k=i;k<=j;k++)                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);            }        }        PRintf("%d/n",dp[1][n]);    }    return 0;}