石子归并

有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。

第一行一个整数n（n<=100）

第二行n个整数w1,w2...wn  (wi <= 100)

dp[i][j]表示合并i到j之间的石头

dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum(i,j))(i<=k<j)

如果只有两堆的时候，dp[i][i+1]=sum(i,i+1)

如果把三堆合起来，就是dp[i][i+2]=min(dp[i][i+1],dp[i+1][i+2])+sum(i,i+2)

以此推到n堆的时候就行了,O^3，貌似看到别人说可以四边形优化？？不懂= =下次遇到要优化的再回来看看

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
#define X first
#define Y second
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define sd(x) scanf("%d",&(x))
#define Pi acos(-1.0)
#define sf(x) scanf("%lf",&(x))
#define ss(x) scanf("%s",(x))
#define maxn 50005
const int inf=0x3f3f3f3f;
const ll mod=1000000007;
int sum[105];
int dp[105][105];
int main()
{
#ifdef local
    freopen("in","r",stdin);
    //freopen("out","w",stdout);
    int _time=clock();
#endif
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>sum[i];
        sum[i]+=sum[i-1];
    }
    for(int v=1;v<n;v++)
    {
        for(int i=1;i<=n-v;i++)
        {
            dp[i][i+v]=inf;
            int j=i+v;
            int tmp=sum[j]-sum[i-1];
            for(int z=i;z<j;z++)
            {
                dp[i][j]=min(dp[i][j],dp[i][z]+dp[z+1][j]+tmp);
            }
        }
    }
    cout<<dp[1][n]<<endl;
#ifdef local
    printf("time: %d
",int(clock()-_time));
#endif
}