区间dp复盘

P1880 [NOI1995] 石子合并 题解复盘

模块：区间动态规划（Interval DP）

类型：区间DP + 前缀和 + 环形DP

目标：求石子合并的最小总代价和最大总代价。

基本信息

解题前・关键信号识别

解题后・外化复盘

为什么要复制数组？

原数组：

4 5 9 4

复制：

4 5 9 4 4 5 9 4

例如：

从第二堆开始断开：

5 9 4 4

对应：

区间 [2,5]

因此：

所有长度为 n 的区间：

[1,n] [2,n+1] ... [n,2n-1]

刚好对应所有断环方式。

为什么要加 sum(l,r)？

例如：

区间：

4 5 9

最后一次一定会变成：

(4 5) + (9)

或者：

(4) + (5 9)

左右两边已经分别合并完成。

最后：

左右两堆还要再合并一次。

最后一次合并后的石子数：

4+5+9=18

因此：

最后一次代价就是：

sum(l,r)

所以状态转移必须写成：

dp[l][k]+dp[k+1][r]+sum(l,r)

为什么枚举区间长度？

因为：

dp[1][4]

依赖：

dp[1][2] dp[3][4] dp[1][3] dp[2][4]

这些都是更短的区间。

因此必须：

长度2 ↓ 长度3 ↓ 长度4 ↓ …… ↓ 长度n

模板：

for(intlen=2;len<=n;len++){for(intl=1;l+len-1<=2*n;l++){intr=l+len-1;for(intk=l;k<r;k++){}}}

AC完整代码

#include<iostream>#include<algorithm>usingnamespacestd;constintN=205;constintINF=1e9;inta[N];ints[N];intmn[N][N];intmx[N][N];intmain(){intn;cin>>n;for(inti=1;i<=n;i++){cin>>a[i];a[i+n]=a[i];}for(inti=1;i<=2*n;i++){s[i]=s[i-1]+a[i];}for(inti=1;i<=2*n;i++){for(intj=1;j<=2*n;j++){mn[i][j]=INF;mx[i][j]=0;}mn[i][i]=0;mx[i][i]=0;}for(intlen=2;len<=n;len++){for(intl=1;l+len-1<=2*n;l++){intr=l+len-1;for(intk=l;k<r;k++){intsum=s[r]-s[l-1];mn[l][r]=min(mn[l][r],mn[l][k]+mn[k+1][r]+sum);mx[l][r]=max(mx[l][r],mx[l][k]+mx[k+1][r]+sum);}}}intansMin=INF;intansMax=0;for(intl=1;l<=n;l++){intr=l+n-1;ansMin=min(ansMin,mn[l][r]);ansMax=max(ansMax,mx[l][r]);}cout<<ansMin<<endl;cout<<ansMax<<endl;return0;}

模型总结

区间DP统一模板

for(len=2;len<=n;len++){for(l=1;l+len-1<=n;l++){r=l+len-1;dp[l][r]=初始化;for(k=l;k<r;k++){dp[l][r]=最优(dp[l][k],dp[k+1][r]);}}}

记忆

看到： ① 求一个区间最优值 ② 最后一步可以拆成左右两部分 ③ 枚举切分位置 ↓ 想到： 区间DP 状态： dp[l][r] ↓ 枚举长度 ↓ 枚举左端点 ↓ 枚举切分点 ↓ dp[l][k]+dp[k+1][r] ↓ 如果最后还需要一次操作 + 区间贡献（如sum(l,r)）

P3146 248 题解复盘

模块：动态规划（Dynamic Programming）

类型：区间DP

目标：通过不断合并相邻且相等的数字，使最终数字最大。

基本信息

解题前・关键信号识别

解题后・外化复盘

为什么这样定义状态？

例如：

1 1 2

区间：

[1,2]

可以：

1 1 ↓ 2

因此：

dp[1][2]=2;

如果：

1 2

不能合并。

则：

dp[1][2]=0;

表示：

这个区间无法最终变成一个数字。

为什么这样转移？

设：

[l......k][k+1......r]

最后一次操作一定是：

左区间 + 右区间

因此：

必须：

左区间已经合并完成 右区间已经合并完成

并且：

最终数字相同

例如：

2 2

才能：

2 2 ↓ 3

因此：

if(dp[l][k]!=0&&dp[l][k]==dp[k+1][r]){dp[l][r]=max(dp[l][r],dp[l][k]+1);}

为什么按区间长度枚举？

因为：

dp[l][r]

依赖：

dp[l][k] dp[k+1][r]

而：

这两个区间一定更短。

所以：

必须：

长度1 ↓ 长度2 ↓ 长度3 ↓ …… ↓ 长度n

AC完整代码

#include<iostream>#include<algorithm>usingnamespacestd;inta[255];intdp[255][255];intmain(){intn;cin>>n;intans=0;for(inti=1;i<=n;i++){cin>>a[i];dp[i][i]=a[i];ans=max(ans,a[i]);}for(intlen=2;len<=n;len++){for(intl=1;l+len-1<=n;l++){intr=l+len-1;for(intk=l;k<r;k++){if(dp[l][k]!=0&&dp[l][k]==dp[k+1][r]){dp[l][r]=max(dp[l][r],dp[l][k]+1);}}ans=max(ans,dp[l][r]);}}cout<<ans;return0;}

模型总结

与石子合并区别

记忆

看到： ① 相邻区间合并 ② 一个区间最终变成一个数字 ③ 左右区间共同决定答案 ↓ 想到： 区间DP ↓ dp[l][r] 表示： 区间最终能合成的数字 ↓ 枚举分割点 k ↓ 左右相等 ↓ +1