题目描述
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式：
输出共2行,第1行为最小得分,第2行为最大得分.
输入样例#1：
4
4 5 9 4
输出样例#1：
43
54
设dp[ i ] [ j ]为区间 [ i , j ]内 j - i + 1个 小堆堆成一个大堆的总分的最小/最大值。
则 dp [ i ] [ j ] ＝两子区间：dp[i][k]、dp[k+1][j]得分之和加上 两个子区间石子的总和，可以用前缀和求的。
#include<bits/stdc++.h>
using namespace std;
char buf[100000],*L=buf,*R=buf;
#define gc() L==R&&(R=(L=buf)+fread(buf,1,100000,stdin),L==R)?EOF:*L++;
template<typename T>
inline void read(T&x) {
char ch=gc(); x=0;
while (ch<'0'||ch>'9')ch=gc();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=gc();
}
int a[220],sum[220],n,dp_min[220][220],dp_max[220][220];
int main() {
memset(dp_min,0x3f3f3f3f,sizeof(dp_min));
memset(dp_max,-0x3f3f3f3f,sizeof(dp_max));
// freopen("in.txt","r",stdin);
read(n);
for(int i=1; i<=n; ++i) {
read(a[i]);
a[n+i]=a[i];//化环为线
}
for(int i=1; i<=2*n; ++i) {
sum[i]=sum[i-1]+a[i];
dp_min[i][i]=0;//区间内只有一个石子，不能合成
dp_max[i][i]=0;
}
for(int l=2; l<=n; ++l) {// ｌ<＝>ｊ－ｉ＋１表示长度，长度小可以推出长度大的，故最外层是ｌ
for(int i=1; i<=2*n+-l; ++i) {
int j=i+l-1;
for(int k=i; k<j; ++k) {
dp_min[i][j]=min(dp_min[i][j],dp_min[i][k]+dp_min[k+1][j]);//子区间总分的和的最小值
dp_max[i][j]=max(dp_max[i][j],dp_max[i][k]+dp_max[k+1][j]);
}
dp_min[i][j]+=sum[j]-sum[i-1];//再加上该次合成的得分，即为区间[ｉ，ｊ]的最终得分。
dp_max[i][j]+=sum[j]-sum[i-1];
}
}
int ans_min=0x3f3f3f3f,ans_max=-0x3f3f3f3f;
for(int i=1; i<=n; ++i) {
ans_min=min(ans_min,dp_min[i][n+i-1]);//遍历长度为ｎ的区间，最小值即为答案。
ans_max=max(ans_max,dp_max[i][n+i-1]);
}
cout<<ans_min<<endl<<ans_max;
return 0;
}