题目链接：https://www.rqnoj.cn/problem/490
题目描述
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入格式
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式
输出共2行,第1行为最小得分,第2行为最大得分.
样例输入
4
4 4 5 9
样例输出
43
54
最开始没看到环形，就以为是普通的石子合并，交了就WA了，题意都没看懂。
好坑啊，不过思路跟普通的石子合并差不多，代码能看懂。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int maxn=;
const int INF=0x3f3f3f3f; int dp1[maxn][maxn],dp2[maxn][maxn]; ///dp1最小 dp2最大
int a[maxn],sum[maxn];
int n; int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d",&n)==)
{
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
a[i+n]=a[i];
}
sum[]=;
for(int i=; i<=n*; i++)
sum[i]=sum[i-]+a[i];
memset(dp1,,sizeof(dp1));
memset(dp2,,sizeof(dp2)); for(int d=; d<n*; d++)
for(int i=; i+d<=n*; i++)
{
int j=i+d;
dp1[i][j]=INF;
dp2[i][j]=-INF;
for(int k=i; k<j; k++)
{
dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+][j]+sum[j]-sum[i-]);
dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+][j]+sum[j]-sum[i-]);
}
} int ans1=INF;
int ans2=-INF;
for(int i=; i<=n; i++)
{
ans1=min(ans1,dp1[i][i+n-]);
ans2=max(ans2,dp2[i][i+n-]);
}
printf("%d\n",ans1);
printf("%d\n",ans2);
}
return ;
}