算法实现题 3-5 石子合并问题
算法描述：
在一个圆形操场的四周摆放着 n 堆石子。现要将石子有次序地合并成一堆。规定每次只
能选相邻的 2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一
个算法，计算出将 n 堆石子合并成一堆的最小得分和最大得分。
算法设计:
对于给定n堆石子,计算合并成一堆的最小得分和最大得分。
数据输入:
第一行是正整数n(1<=n<=100),表示有n堆石子。第2行有n个数，分别表示每堆石子的个数。
输入样例：
4
4 4 5 9
数据输出:第1行的数是最小得分，第2行中的数是最大得分
输出样例:
43
54
这次的石子问题是成环的，基础篇看上一篇博客这里?基础篇
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n ;
const int N=200;
int sum[N],Min[N][N],Max[N][N];
int a[N];
int main()
{memset(Min,INF,sizeof Min); //数组初始化memset(Max,0,sizeof Max);cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i+n]=a[i];//环形，复制一遍区间}for(int i=1;i<=2*n;i++){Min[i][i]=0;Max[i][i]=0;sum[i]=sum[i-1]+a[i];//前缀和}
//区间dp的基础for(int len=2;len<=n;len++){for(int l=1;l+len-1<2*n;l++){int r=l+len-1;for(int k=l;k<r;k++){Min[l][r]=min(Min[l][r],Min[l][k]+Min[k+1][r]+sum[r]-sum[l-1]);//状态转化方程Max[l][r]=max(Max[l][r],Max[l][k]+Max[k+1][r]+sum[r]-sum[l-1]);}}}int minn=INF, maxx=0;//每个元素都可能为第一堆石子for(int i=1;i<=n;i++){minn=min(minn,Min[i][i+n-1]); //Min[1,n],f[2,n+1]..f[n,2n-1]maxx=max(maxx,Max[i][i+n-1]); //Max[1,n],g[2,n+1]..g[n,2n-1]}cout << minn << endl << maxx;}