石子合并

类似题目：https://ac.nowcoder.com/acm/problem/50493 石子位置成一个环(就是多存一遍石子，跑2*n
大致题意： 个石子，每个石子有一定的价值，每次可以合并相邻个石子，合并的代价是两个石子的价值和，合并完后两个石子的价值累加一成石子的价值，问将 个石子合并成一个石子的最小代价是多少。

分析:

• 考虑子问题,对于区间 的石子合并成一个石子，更小的子问题就是区间已经分成了两个石子然后合并成一个石子，那么代价其实就是区间所有石子价值和(用前缀和 维护)。假如我们已经得到了 , 的最优合并解，那么对于 的最优解应该是: .
  表示当前子问题合并的代价。
• 那么如何抉择循环条件，我们首先要解决小的子区间，那么最外层 循环从1开始遍历表示子区间的右边界，次外层循环从 开始递减至1表示子区间的左边界，内层循环 从左边界枚举到右边界-1，这样每次选择的子区间都可以保证更小的子问题已经得到解决，可以进行转移。

#include<bits/stdc++.h>


using namespace std;
typedef long long ll;

int a[305],sum[305],dp[305][305];




int main()
{
    int n;
    cin>>n;
    memset(dp,0x3f,sizeof(dp));
    for( int i=1;i<=n;i++ ) cin>>a[i],sum[i]=sum[i-1]+a[i];

    for( int j=1;j<=n;j++ )
    {
        for( int i=j;i>=1;i-- )
        {
            if( i==j ) dp[i][j]=0; 
            for( int k=i;k<j;k++ )
            {
                 dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1],dp[i][j]);
            } 
        }
    }
    cout<<dp[1][n]<<endl;
}