题目描述
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入输出格式
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式：
输出共2行,第1行为最小得分,第2行为最大得分.
--------------------------------------------------------
环形DP，前缀和，O(n3)即可
可以i降序j升序，也可以枚举长度
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=<<,INF=1e9;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,a[N],mx=,mn=INF;
int f[N][N],s[N],d[N][N];
void dp(){
for(int i=;i<=*n;i++)for(int j=;j<=*n;j++) d[i][j]=INF,d[i][i]=; for(int i=;i<=*n;i++) s[i]=s[i-]+a[i];
// for(int i=2*n-1;i>=1;i--)
// for(int j=i+1;j<=2*n&&j-i<n;j++)
// for(int k=i;k<j;k++){
// f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
// d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]+s[j]-s[i-1]);
// }
for(int l=;l<n;l++)
for(int i=;i<=*n;i++){
int j=min(*n,i+l);
for(int k=i;k<j;k++){
f[i][j]=max(f[i][j],f[i][k]+f[k+][j]+s[j]-s[i-]);
d[i][j]=min(d[i][j],d[i][k]+d[k+][j]+s[j]-s[i-]);
}
} }
int main(int argc, const char * argv[]) {
n=read();
for(int i=;i<=n;i++) a[i]=read(),a[i+n]=a[i];
dp();
for(int i=;i<=n;i++) mx=max(f[i][i+n-],mx),mn=min(mn,d[i][i+n-]);
printf("%d\n%d",mn,mx);
return ;
}