区间 dp 学习笔记

· · 算法·理论

入门

首先了解区间 dp 的含义，顾名思义，是处理区间问题的一种动态规划形式。

首先你得了解动态规划是怎么个事，在这里就不过多赘述。

首先看 P1775。

很显然，小根堆等贪心无法通过，因为并不是可以合并任意两堆。

我们思考，这题需要什么。

这就是区间 dp 的基本思路：设计 dp_{i,j} 为将 i \sim j 合并的代价。

那我们应该怎么处理这个区间呢？

我们要建立一个思想，就是分治思想，虽然这和分治不太一样。

我们要把整个序列分成两个我们已经处理好的序列去做 dp，在 l \sim r 枚举断点 k。因为 l \sim k 和 k+1 \sim r 都已经被处理好了，所以我们可以将 l \sim k 和 k+1 \sim r 看成两个点。我们已经知道了前一个点合并的最小代价，和后一个点合并的最小代价，于是就可以求出以 k 为断点合并 l \sim r 的最小值，再取一个 k 在 l \sim r 中合并的最小值赋给 dp_{l,r} 即可。

我们再看 P3146。

本题需要有一定改变。

首先我们会发现一个很重要的问题：序列不一定能合并完！

不过没有关系，我们同样可以发现，最后增大的那个数一定是由很多数合成的。

我们允许 l \sim r 区间无法合并，无法合并的话 dp_{l,r} = 0，不会影响 dp 结果。

但是我们发现，可能整个序列无法合并，所以 ans 先必须取到 a_i 的最大值。

然后依旧是在 l \sim r 寻找断点 k，仅仅是 dp 转移式相对上题有所改变，变成了 \max(dp_{l,r},dp_{l,k}+1)。

其次，这是一个有限制的区间 dp，因为只有当 dp_{l,k} 和 dp_{k+1,r} 相等时才可以转移。

#include <bits/stdc++.h>
using namespace std;

int a[255];
int dp[255][255];
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) ans=max(ans,a[i]);
    for(int i=1;i<=n;i++) dp[i][i]=a[i];
    for(int i=1;i<=n;i++){
        for(int l=1;l+i-1<=n;l++){
            int r=l+i-1;
            for(int z=l;z<r;z++){
                if (dp[l][z]==dp[z+1][r]&&dp[l][z]!=0){
                    dp[l][r]=max(dp[l][r],dp[l][z]+1);
                    ans=max(ans,dp[l][r]);
                 }
             }
         }
     }
     cout<<ans<<endl;
    return 0;
}

本题代码。

再一次提示大家一个问题，在区间 dp 循环时一定要有一个好习惯，先枚举长度，再枚举起点，最后枚举断点，这样就可以少犯一些错误，也更清晰一些。

进阶

首先我们选择一道难度中等的例题：P4170。

注意到数据范围 n \le 50，很容易想到区间 dp。

本题我们可以想到一个很简单的转移：

对于这种做法很容易就扔掉了，因为太假了。

我们发现一个问题，当 l,r 区间 a_l 与 a_r 相同时，我们不需要增加一次刷，而可以一次刷完。

所以对于这种，dp_{l,r} = \min(dp_{l,r-1},dp_{l+1,r})。

总结一下，这种区间 dp 属于有特殊情况不通过区间转移的区间 dp。

我取个名字叫做限制型区间 dp。

再看第二道例题：P5851。

与上一题相似，这也是限制型区间 dp。

作者认为本题有难度，可能是作者太蒟了，花了不少时间才弄懂是怎么个事，或是理解的确有一定难度。

我们发现在本题中，与上题相似，仅仅是区间枚举并不可以。但与上题不同的地方是，这题的限制需要二次枚举断点。

考虑 dp_{l,r} 代表 l \sim r 的派能获得的最大体重（不一定要吃完）。

我们首先老套路摆上：

但是怎么更好的求值呢？

考虑一种情况，因为每个奶牛至少需要一个派，那么，我们再枚举断点 k。

考虑 g_{k,l,r} 代表在所有能吃到 k 号派，其范围在 l \sim r 之间的奶牛体重最大值。

注意一个很重要的地方：这个奶牛一定没有被算到 dp_{l,k-1} 和 dp_{k+1,r} 里，因为其范围是 l,r，不会只吃前述范围的。这里我卡了很久，因为题解无一叙述了这一点。（可能是我唐了）

然后考虑 g_{k,l,r} 的求值方式。与上一题类似，还是用两边扩张的方法即可。

然后没什么了，自己随便找点题练习吧，如果发现有别的类型可以联系我补。