题目描述
在一个园形操场的四周摆放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。
#include<cstdio>
#include<iostream>
#define maxn 206
using namespace std;
int n,sum[maxn];
int dpmin[maxn][maxn],dpmax[maxn][maxn];
int main()
{
scanf("%d",&n);
for(int a,i=;i<=n;i++)
{
scanf("%d",&a);
sum[i]=sum[i-]+a;
sum[i+n]=sum[i];
}
for(int i=;i<n;i++)
sum[i+n]+=sum[n];
for(int len=;len<n;len++)
for(int i=;i<=n*--len;i++)
{
int j=i+len;
int res1=0x7fffffff;
int res2=-;
for(int k=i;k<j;k++)
{
res1=min(res1,dpmin[i][k]+dpmin[k+][j]+sum[j]-sum[i-]);
res2=max(res2,dpmax[i][k]+dpmax[k+][j]+sum[j]-sum[i-]);
}
dpmin[i][j]=res1;
dpmax[i][j]=res2;
}
int MIN=0x7fffffff,MAX=;
for(int i=;i<=n;i++)
MIN=min(dpmin[i][i+n-],MIN),MAX=max(dpmax[i][i+n-],MAX);//!dp[i][i+n-1]
printf("%d\n%d",MIN,MAX);
return ;
}