描述
http://codevs.cn/problem/2102/
2102 石子归并 2
时间限制: 10 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 Description
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入描述
Input Description
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出描述
Output Description
输出共2行,第1行为最小得分,第2行为最大得分.
样例输入
Sample Input
4
4 4 5 9
样例输出
Sample Output
43
54
数据范围及提示
Data Size & Hint
经典的区间动态规划。
分析
枚举起点即可.
#include <bits/stdc++.h>
using namespace std; const int maxn=+,INF=0x7fffffff; int n,ans1,ans2;
int s[maxn<<],dp1[maxn][maxn],dp2[maxn][maxn]; void solve(){
ans1=INF, ans2=-INF;
for(int q=;q<=n;q++){
for(int r=;r<=n;r++)
for(int i=q;i<=q+n-r;i++){
int j=i+r-;
dp1[i-q+][j-q+]=INF; dp2[i-q+][j-q+]=-INF;
for(int k=i;k<j;k++){
dp1[i-q+][j-q+]=min(dp1[i-q+][j-q+],dp1[i-q+][k-q+]+dp1[k+-q+][j-q+]+s[j]-s[i-]);
dp2[i-q+][j-q+]=max(dp2[i-q+][j-q+],dp2[i-q+][k-q+]+dp2[k+-q+][j-q+]+s[j]-s[i-]);
}
}
ans1=min(dp1[][n],ans1);
ans2=max(dp2[][n],ans2);
}
printf("%d\n%d\n",ans1,ans2);
}
void init(){
scanf("%d",&n);
for(int i=;i<=n;i++){
int t; scanf("%d",&t);
s[i]=s[i-]+t;
}
for(int i=n+;i<=n*;i++) s[i]=s[i-n]+s[n];
}
int main(){
init();
solve();
return ;
}