codevs1048石子归并

#include<iostream>
#include<cstdio>
#define MAXN 105
#define INF 0x3f3f3f3f
using namespace std;
int max(int x,int y){
    return x>y?y:x;    
} 
int n,w[MAXN],a[MAXN][MAXN],z[MAXN];
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        scanf("%d",&z[i]),w[i]=w[i-1]+z[i];
    for(int z=1;z<n;++z)
    {
        for(int i=1;i+z<=n;++i)
        {
            int j=i+z,sum=w[j]-w[i-1];
            a[i][j]=INF;
            for(int zz=i;zz<j;++zz)
            {
                a[i][j]=min(a[i][j],a[i][zz]+a[zz+1][j]+sum);
            }
        }
    }
    printf("%d",a[1][n]);
}