Description
在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。
规定每次只能选相邻的两堆石子合并成新的一堆，并将新得的这堆石子数记为该次合并的得分。
试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
Input
输入的第一行是正整数n，1 ≤ n ≤100，表示有n堆石子围成环形。
第二行有n个数，分别表示每堆石子的个数。
Output
输出的第一行中的数是最小得分；第二行中的数是最大得分。
Sample Input
4
4 4 5 9
Sample Output
43
54
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int a[],n;
int dp0[][],dp1[][];
/// dp0[][],dp1[][]分别维护最小值和最大值
/// dp0[i][j]保存的是 以i为起点j为长度 时的总得分
int sum(int i,int l)
{
int s=;
for(int j=i;j<i+l;j++)
s+=a[j%n];
return s;
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++) scanf("%d",&a[i]);
for(int l=;l<=n;l++)
for(int i=;i<n;i++)
{
dp0[i][l]=INF, dp1[i][l]=;
for(int j=;j<l;j++)
{
int a=dp0[i][j],b=dp0[(i+j)%n][l-j],
c=dp1[i][j],d=dp1[(i+j)%n][l-j];
dp0[i][l]=min(dp0[i][l],a+b+sum(i,l));
dp1[i][l]=max(dp1[i][l],c+d+sum(i,l));
/// a+b + sum()
/// 左右区间的总得分 + 合并左右区间的得分
/// 合并两个区间的得分 = 两区间内所有元素之和
}
}
int ans0=INF,ans1=;
for(int i=;i<n;i++)
ans0=min(ans0,dp0[i][n]),
ans1=max(ans1,dp1[i][n]);
printf("%d\n%d\n",ans0,ans1); return ;
}