合并石子（动态规划）
Description
在一个圆形操场的四周摆放 N 堆石子,现要将石子有次序地合并成一堆
.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，
记为该次合并的得分。
试设计出一个算法,计算出将 N堆石子合并成 1堆的最小得分和最大得分。
Input
数据的第 1行是正整数 N，表示有 N 堆石子, N <= 500。
第 2 行有 N 个整数，第 i个整数 ai 表示第 i 堆石子的个数, ai <= 50。
Output
输出共 2 行，第 1 行为最小得分，第 2 行为最大得分。
Sample Input
4
4 5 9 4
Sample Output
43
54首先理解题意，笔者看到这道题时首先想到的是贪心，仔细分析后发现题上没说石子根据一定顺序来摆放，易证局部最优解不一定是问题最优解，没有贪心性质，不能用贪心
然后需要强调的是，该题是一个圆形结构
这里为了方便理解，我们先将其简化为线性结构
先看一个简单的子问题
现在一共有三堆石头，每堆石子的数量分别是3，4，11。求合并成一堆石头的最小得分。
对于这个问题，只有两种选择：
前两堆石头合并再和第三堆石头合并。
3+4=7 ——> 7 石堆变为（7， 11）
7+11=18——>18 石堆变为（18）
cost=7+18=25
后两堆石头合并再和第一堆石头合并。
4+11=15——>15 石堆变为（3，15）
3+15=18——>18 石堆变为（18）
cost=15+18=33易看出先合并前两堆的石子的花费比较小，不同的合并方式会造成不同的得分。同时可以发现这两种方法最后一次的得分就是石头的总数。
现在我们用一个数组arr[]按顺序保存每个位置的石头数量。
arr[]={3,4,11}前缀和数组sum[i]表示前i堆石头的总和
sum[0]=3;
sum[1]=7;
sum[2]=18;最后用一个二维数组dp[i][j]表示从第i堆到第j堆石头合并的最小分数。
1）每堆石头跟自己合并的分数都是0。
dp[0][0]=dp[1][1]=dp[2][2]=0
2）相邻两堆石头的最小合并分数只有一种可能。
dp[0][1]=3+4=7, dp[1][2]=4+11=15
3）剩下的就是不相邻石头的合并最小花费。
设一个k∈[i,j]；
dp[i][j]=dp[i][k]+dp[k][j]+sum[i][j];
那么从i到j的所有花费都可以表示出来了,取一个使得dp[i][j]最小的值。
求最大花费时同理，只需将相关变量进行改变即可最后回到原始问题，我们是一个圆形结构，此时
输入4 5 9 4，还要考虑4 4 5 9，9 4 4 5和5 9 4 4
因此我们每次都改变输入数组，最后最小取得最小，最大取得最大即可
详情可以看代码
#include<cstdio> #include<algorithm> using namespace std; int dp1[505][505];//定义dp1[i][j]表示从第i堆到第j堆石子合并的最小得分 int dp2[505][505];//定义dp1[i][j]表示从第i堆到第j堆石子合并的最大得分 int n,maxn=0x3f3f3f3f,ans1=maxn,ans2=0; int arr[505],sum[505]; void pc(){ int temp=arr[0]; for(int i=0;i<n;i++) arr[i]=arr[i+1]; arr[n-1]=temp; } //满足环形排列 int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&arr[i]); } for(int count=1;count<=n;count++){//4 5 9 4 5 9 4 4 9 4 4 5 4 4 5 9 // for(int i=0;i<n;i++){ // printf("%d ",arr[i]); // } // printf("\n"); sum[0]=arr[0]; for(int i=1;i<n;i++){ sum[i]=sum[i-1]+arr[i];//前缀和数组 } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ dp1[i][j]=maxn;//求最小得分因此初始化为最大值 dp2[i][j]=0;//求最大得分因此初始化为最小值 if(i==j){//最小子问题 自己不能和自己合并因此i=j时初始化为0 dp1[i][j]=dp2[i][j]=0; } } } for(int k=2;k<=n;k++){//从大小为2的子问题开始求解 for(int i=0;i<n;i++){//起点 int j=i+k-1;//终点 if(k==2){//只有两堆石子时结果就是两堆石子相加 dp1[i][j]=arr[i]+arr[j]; dp2[i][j]=arr[i]+arr[j]; }else{ int temp=sum[j]-sum[i-1];//最后一次合并固定加上所有数之和 for(int t=i;t<j;t++){ dp1[i][j]=min(dp1[i][j],dp1[i][t]+dp1[t+1][j]+temp); dp2[i][j]=max(dp2[i][j],dp2[i][t]+dp2[t+1][j]+temp); } } } } // printf("求最小\n"); // for(int i=0;i<n;i++){ // for(int j=0;j<n;j++){ // printf("%d ",dp1[i][j]); // } // printf("\n"); // } // printf("求最大\n"); // for(int i=0;i<n;i++){ // for(int j=0;j<n;j++){ // printf("%d ",dp2[i][j]); // } // printf("\n"); // } //最后在所有的情况中取最小值即可 ans1=min(ans1,dp1[0][n-1]); ans2=max(ans2,dp2[0][n-1]); pc(); } printf("%d\n%d\n",ans1,ans2); return 0; }读者可以将注释中的内容解开调试方便理解