4457: 【入门】石子合并（环形）(2058)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
在一个圆形操场的四周摆放 堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法，计算出将 堆石子合并成 堆的最小得分和最大得分。
输入
数据的第 行是正整数 ，表示有 堆石子。
第 行有 个整数，第 个整数 表示第 堆石子的个数。
。
输出
输出共 行，第 行为最小得分，第 行为最大得分。
样例输入 复制
4
4 5 9 4样例输出 复制
43
54提示
#include<bits/stdc++.h>
using namespace std;
/*
将数据规模翻倍，将a数组完整接贝一遍求
区间最长长度为的情况下，合并得到的最优解
再从每个可能的起点出发，打播台求最小、最大值
*/
const int N= 410;
int a[N*2],s[N*2]; //s:前缀和
int mi[N*2][N*2],ma[N*2][N*2];
int n;
int main(){
cin>>n; //初始化
memset(mi,0x3f,sizeof(mi));
memset(ma,-0x3f,sizeof(ma));
for(int i= 1;i<= n;i++){
cin>>a[i];
a[i+n]= a[i]; //数组完整的赋值一遍
}
for(int i=1;i<= n*2;i++) {
s[i]=s[i-1]+a[i];
mi[i][i]= 0;
ma[i][i]= 0;
}
//初始化
//区间dp求解
//穷举所有可能的区间长度
for(int len=2;len<= n;len++){
//穷举区间的左端点
for(int i=1;i+len-1<= n* 2;i++){
//右端点
int j=i+len-1;
//穷举分割点
for(int k= i;k< j;k++){
mi[i][j]=min(mi[i][j],mi[i][k]+mi[k+1][j]+s[j]-s[i-1]);
ma[i][j]=max(ma[i][j],ma[i][k]+ma[k+1][j]+s[j]-s[i-1]);
}
}
}
//穷举所有可能的出发点，打擂台求最小、最大
int minn = INT_MAX,maxn = INT_MIN;
for(int i= 1;i<= n;i++){
minn = min(minn,mi[i][i+n-1]);
maxn = max(maxn,ma[i][i+n-1]);
}
cout<<minn<<endl<<maxn;
return 0;
}