石子合并（一）

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