luogu P1880 [NOI 1995]石子合并(区间dp)
题面传送门
一、确定算法
第一眼看见：最小得分与最大得分，便想到要用贪心或dp
贪心能用吗？不能，因为只有相邻两堆才能合并，这样就无法贪心啦！
hack数据： 5
8 4 6 3 5所以，此题正解就是 区间dp
二、前置操作
首先，发现要在一个首尾相连的环上dp并不方便，于是可以 断环为链
假设输入的数是a[1],a[2],……,a[n]
那么使a[n+1]=a[1],a[n+2]=a[2],……,a[2*n]=a[n]
你会惊讶地发现n个数的环上的每一段都在2*n个数的链上了
于是就在链上dp等价于在环上dp三、dp流程
dp的状态转移方程是很重要的1、状态
设dp1[i][j]表示把从i到j的石子合并为一堆的最小得分，dp2[i][j]表示把从i到j的石子合并为一堆的最大得分（i<j）2、转移方程
以最小值为例
假设存在k使得 将i到k合为一堆的最小得分(a堆)+将k+1到j合为一堆的最小得分(b堆)+将a堆与b堆合并的得分 < 将i到j合为一堆的最小得分 时，更新dp[i][j]
即dp1[i][j]=min(dp1[i][k]+dp1[k+1][j]+将a堆与b堆合并的得分,dp1[i][j])
所以现在唯一的未知量就是将a堆与b堆合并的得分了
观察到，a堆的石子个数使a[i]+a[i+1]+……+a[k],b堆的石子个数是a[k+1]+a[k+2]+……+a[j]
所以将a堆与b堆合并的得分=a[i]+a[i+1]+……+a[j]
故dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+a[i]+a[i+1]+……+a[j])
同理dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+a[i]+a[i+1]+……+a[j])3、答案输出
最小值:minn=min(minn,dp1[i][i+n-1])
最大值:maxx=max(maxx,dp2[i][i+n-1]) （1<=i<=n）四、注意细节
细节决定成败1、初始化
minn=0x7fffffff,maxx=0
dp1[i][j]=0x3f3f3f3f(循环内)2、前缀和优化
观察到，每次状态转移时，都要计算a[i]+a[i+1]+……+a[j],有些麻烦，所以我们可以与计算前缀和，则a[i]+a[i+1]+……+a[j]=sum[j]-sum[i-1]
前缀和的计算方法不会的话，就看代码吧3、数组大小
一定要注意！无论是存每堆的石子数量的a数组，还是dp1，dp2数组都要开到201！4、注意
dp过程的循环要先枚举dp区间的长度，再枚举左端点，右端点也可以求出来了，再枚举k，具体的看代码吧code:
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N=205;
int a[N],dp1[N][N],dp2[N][N],sum[N];
int n,minn=0x7fffffff,maxx;
int read(){
int cnt=0; char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') cnt=cnt*10+c-'0',c=getchar();
return cnt;
}
void input(){
n=read();
for(int i=1;i<=n;i++) a[i]=read(),a[i+n]=a[i]; //断环为链
for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i]; //前缀和
memset(dp1,0x3f3f3f3f,sizeof(dp1));
for(int i=1;i<=n;i++) dp1[i][i]=0; //初始化
}
void dp(){
for(int len=2;len<=n;len++) //阶段
for(int i=1;i<=2*n-len+1;i++){ //左端点
int j=i+len-1; //右端点
for(int k=i;k<j;k++){ //决策
dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]); //状态转移
dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]);
}
}
}
void output(){
for(int i=1;i<=n;i++)
minn=min(minn,dp1[i][i+n-1]),maxx=max(maxx,dp2[i][i+n-1]); //答案
printf("%d\n%d\n",dp1[1][n],dp2[1][n]);
}
int main(){
input();
dp();
output();
return 0;
}