P1880 [NOI1995] 石子合并
P1880 [NOI1995] 石子合并
/*
P1880 [NOI1995] 石子合并
首先由链型石子合并模板入手思考比较朴素的解法，
因为n堆石子最多合并n-1次，每次合并相当于在原来的n个点中连边，显然最后一定剩下两个点没有连边，这样的合并实际上就是链型的，
一个环可以根据分割边的不同形成不同的链，只需要在最外层循环分割点，然后进行标准的链型石子合并dp即可，但复杂度O(n^4)，
在上述方法中，实际上在不同的分割点dp时，使用的很多区间是重复的，只需要把原序列当成一条链，在后面紧接着复制一遍，
在[1,2n-1]的范围中依此枚举长度为2~n的区间即可，这对应了前一种做法的所有情况且不会用到重复的区间，复杂度O(n^3)。
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=210,inf=0x3f3f3f3f;
int n,s[N],a[N],dpmin[N][N],dpmax[N][N];
int main()
{
memset(dpmin,inf,sizeof dpmin);
memset(dpmax,-inf,sizeof dpmax);
scanf("%d",&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++) s[i]=s[i-1]+a[i],dpmax[i][i]=dpmin[i][i]=0;//注意赋初值
for(int len=1;len<n;len++)
for(int i=1;i+len<=2*n;i++)//左端点最多可以枚举到2n-len
{
int j=i+len;
for(int k=i;k<j;k++)
dpmax[i][j]=max(dpmax[i][j],dpmax[i][k]+dpmax[k+1][j]+s[j]-s[i-1]),
dpmin[i][j]=min(dpmin[i][j],dpmin[i][k]+dpmin[k+1][j]+s[j]-s[i-1]);
}
int ansmax=-inf,ansmin=inf;
for(int i=1;i<n;i++) ansmax=max(ansmax,dpmax[i][i+n-1]),ansmin=min(ansmin,dpmin[i][i+n-1]);//在所有切成链的方式中取最值
printf("%d\n%d",ansmin,ansmax);
return 0;
}