P1880 [NOI1995]石子合并
ChangYiMing
·
·
个人记录
石子合并
这里的石子合并是 区间DP ，不是贪心（下面会讲为什么）。
这是一道 非常^2147483647经典的 区间DP ，它代表了这一大类题，只不过这道题是环形的，需要加额外操作。
时间复杂度：0(n^3) 。(两个端点；一个中转点，用来更新两端点)
题目
【题目描述】
在一个圆形操场的四周摆放 N 堆石子,现要将石子有次序地合并成一堆。规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法,计算出将 N 堆石子合并成 1 堆的最小得分和最大得分。(两问)
【输入格式】
第 1 行是正整数 N，表示有 N 堆石子。
第 2 行有 N 个整数，第 i 个整数 a_i表示第 i 堆石子的个数。
【输出格式】
输出共 2 行，第 1 行为最小得分，第 2 行为最大得分。
【输入输出样例】
输入：
4
4 5 9 4
输出:
43
54
【说明/提示】
对于 100% 的数据 ：1≤N≤100，0 ≤a_i≤ 20 。
基本思路
-
首先， 这道题不能用贪心 ，这个很好理解，因为其取相邻两个石子合并，不是任意两石子，若是后者，就是贪心。
-
解决关于环的问题，首先想到的是 化环为链 。即将这条链 延长 2 倍 ，扩展成 2n-1 堆，其中第 1 堆与 n+1 堆完全相同，第 i 堆与 n+i 堆完全相同，这样我们只要对这 2n 堆动态规划后， 枚举: f(1,n),f(2,n+1),…,f(n,2n-1) , 取最优值即可。
1.状态
2.状态转移
3.初值
注，最终答案很明显，是。。。（自己思考，其实已经讲过了）。
代码
```cpp
#include <stdio.h>
#define ll long long
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)<(y)?(x):(y)
using namespace std;
int a[205],sum[205],f1[205][205],f2[205][205];
int read(){
int a1=0,k1=1;char c1=getchar();
while(c1<'0'||c1>'9'){
if(c1=='-')k1=-1;c1=getchar();
}
while(c1>='0'&&c1<='9'){
a1=a1*10+c1-'0';
c1=getchar();
}
return a1*k1;
}
int main(){
int n=read(),ans1=0x3f3f3f3f,ans2=0;
for(int i=1;i<=n;i++){
a[i]=read();
a[i+n]=a[i]; //化环为链,即扩大一倍
}
for(int i=1;i<=n*2;i++){
sum[i]=sum[i-1]+a[i]; //前缀和
}
for(int i=1;i<=n*2;i++){
for(int j=i+1;j<=n*2;j++){
f2[i][j]=0x3f3f3f3f;
}
}
for(int len=2;len<=n;len++){ //枚举合并石子的长度，长度不能大于n
for(int i=1;i+len-1<=n*2;i++){ //这里i+len-1是右端点，不能超过2*n
int j=i+len-1; //右端点
for(int k=i;k<j;k++){ //正下方 k+1，因为 k+1<=j ，所以这里 k 从i枚举到 j-1
f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+sum[j]-sum[i-1]);
f2[i][j]=min(f2[i][j],f2[i][k]+f2[k+1][j]+sum[j]-sum[i-1]);
}
}
}
for(int i=1;i<=n;i++){
ans1=min(ans1,f2[i][i+n-1]); //第一问，最小值
ans2=max(ans2,f1[i][i+n-1]); //第二问，最大值
}
printf("%d\n%d\n",ans1,ans2);
return 0;
}
```
## 原题：
[【洛谷】P1880 [NOI1995]石子合并](https://www.luogu.com.cn/problem/P1880)