考前抱佛脚——普及+/提高-的DP套路

前记

备战 CSP2022-J/S，基础算法觉得没大问题，图论觉得差不多，数据结构觉得差很多但不想学，“迫不得已”复习 DP。（太基础的就没写，大多数为理论知识。）

本人学术尚浅，有问题请指出。

1.线性动态规划

线性动态规划，也就是每个状态都可以由编号比它小的点转移；作为最简单的一类动态规划，其更像是 DP 的引入，更为简单，反而不像背包、区间、树形 DP 等有较为通用的思路，更重要的是思想。LIS 问题就很好的体现了线性动态规划的思想。

☆1.1 LIS 问题

• 给定一个长为 的序列 ，求这个序列的最长单调上升子序列长度。
• 。

DP 思路：

显然最简单的思路是设 为以 结尾的最长上升子序列的元素个数，则状态转移方程为：

最后答案即为 。

众所周知，DP的复杂度为 ，即 。

尽管时间复杂度不够优，但充分体现了线性动态规划的常见思路，其实一般情况下，简单的最长 XX 子序列问题都可以在 的时间复杂度下得以解决。

贪心 + 二分 思路：

虽然是 DP 的经典模型，但是却是贪心 + 二分的产物。

设 为最长上升子序列中第 位最小可以放置的数值。则每次更新，我们要找到对于当前点 ，使用二分找到第一个大于等于 的位置，故状态转移方程为：

特别的如果用 表示现在的最长上升子序列的长度，则如果 ， 。

最后答案即为 ,时间复杂度为 。

// AT_chokudai_S001_h LIS
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1e5+10;
int n,cnt,a[MAXN],f[MAXN];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    f[++cnt]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]>f[cnt]) f[++cnt]=a[i];
        else
        {
             int k=lower_bound(f+1,f+cnt+1,a[i])-f;
             f[k]=a[i];
        }
    }
    printf("%d\n",cnt);
    return 0;
}

1.2 LCS 问题

• 给出 的两个排列 和 ，求它们的最长公共子序列。
• 对于 的数据， 。

（朴素的 算法不再赘述）

在了解了 LIS 问题 的基础上，LCS 问题就变得十分简单了。

对于两个排列，我们将其重新标号：

3 4 5 1 2 1 2 3 4 5

1 3 5 4 2 4 1 3 2 5

这样的话我们可以看作更改后的 序列是单调递增的，所以两个序列的最长公共子序列也是单调递增的，然后在更改后的 序列中找最长上升子序列即可。

// P1439 【模板】最长公共子序列
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1e5+10;
int n,a[MAXN],b[MAXN],f[MAXN],lis[MAXN],tot;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[a[i]]=i;
    for(int i=1;i<=n;i++) scanf("%d",&b[i]),b[i]=f[b[i]];
    lis[tot]=0;
    for(int i=1;i<=n;i++)
    {
        if(b[i]>lis[tot]) lis[++tot]=b[i];
        else
        {
            int k=lower_bound(lis+1,lis+1+tot,b[i])-lis;
            lis[k]=b[i];
        }
    }
    printf("%d\n",tot);
    return 0;
}

2. 背包问题

背包其实与其他的 DP 不太相同，但应用最为广泛，还可以搬到树上，那么简单的东西，直接说多重背包吧。

2.1 二进制拆分优化多重背包

• 有 种物品的一个容量是 的背包。

• 第 种物品最多有 件，每件体积是 ，价值是 。

• 求解最大价值和。

暴力做法就是将其看为 01 背包问题，时间复杂度为 。

我们考虑到，将其看成 个物品，有点浪费，我们可否将其拆分成更少的物品，使 可以使用这些物品凑出，于是我们将其拆分成二的倍数，即 ，最后剩下的再单独拆分成一整个，这样便可以将其拆分成 个物品已达到同样的效果，则现在的时间复杂度为 ，足已通过此题。

☆2.2 单调队列优化多重背包

若将上一题数据范围改为：

我们则需要使用一种 的算法实现。

我在学习单调队列优化多重背包时，所看到过的博客基本都是从最朴素的 DP 进行推导，但是很容易就把初学者绕蒙。所以我还是决定以我的思路去写我的学习笔记。

首先我们还是像普通的背包那样，设 为体积和为 时的价值和最大值。

对于一个物品，我们知道它的 ，我们在通过这个物品进行状态转移时， 只能从 转移过来，也就是说我们可以按照 分组，每组之间互不影响。

在每组之中，如果我们将每个 按照 编号，设当前的 编号为 ，则 可以从编号 且 的编号转移过来， （编号为 ）可以从编号 且 的编号转移过来，像极了滑动窗口，便可以用单调队列优化。

但是我们在维护最大值的时候，从每一个合法位置转移过来的时候，所要取的当前物品的个数不同，怎样才能直接维护？我们只需要在统计值的时候，将 赋值为 ，也就是把它们都默认为 的值，在赋值的时候，再加上 （这里 的值已经发生了改变），这样我们在单调队列中就可以简单的比较大小。

这样我们插入新元素的操作即为：

pos[++tail]=j/v,num[tail]=f[j]-j/v*w;

弹出队首:

if(head<=tail&&(j/v-pos[head])>s) head++;

弹出队尾：

while(head<=tail&&num[tail]<f[j]-j/v*w) tail--;

DP 的状态更新即为：

//由于我们先放入新元素，再更新（否则f[i]会改变），所以tail-1
if(head<=tail-1) f[j]=num[head]+j/v*w;

在单调队列优化多重背包的时候，每种状态在考虑每个物品时只会被更新一次，且更新一次为 ，则总时间复杂度为 。

完整代码即为：

// AcWing 6. 多重背包问题 III
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*f;
}
const int MAXN=1010,MAXV=2e4+10;
int n,V,f[MAXV],p[MAXN],num[MAXV],pos[MAXV],head,tail;
main()
{
    n=read(),V=read();
    for(register int i=1,v,w,s;i<=n;++i)
    {
        v=read(),w=read(),s=read();
        for(register int d=0;d<v;++d)
        {
            head=1,tail=0;
            for(register int j=d;j<=V;j+=v)
            {
                if(head<=tail&&(j/v-pos[head])>s) head++;
                while(head<=tail&&num[tail]<f[j]-j/v*w) tail--;
                pos[++tail]=j/v,num[tail]=f[j]-j/v*w;
                if(head<=tail-1) f[j]=num[head]+j/v*w;
            }
        }
    }
    printf("%lld\n",f[V]);return 0;
}

3.区间动态规划

区间&环形 DP 其实也就是一种套路；

3.1区间 DP

区间 DP 的常见套路是大区间的状态可以由小区间转移过来，这样的话我们状态的设计就要与区间相关，一般设 表示从 到 的这个区间的状态，同时大区间由小区间转移，我们要先按照区间长度由小到大进行转移。

一般代码如下：

for(int i=1;i<=n;++i) f[i][i]=a[i]// 赋初值
for(int p=1;p<n;++p) //枚举区间长度为 p+1
{
  for(int i=1;i+p<=n;++i)  //枚举区间左端点为i
  {
    int j=i+p; //右端点为j
    for(int k=i;k<j;++k) //枚举中间点
    {
       f[i][j]=f[i][k]+f[k+1][j]; //由 i--k 和 k+1--j 转移过来
      //一般情况大区间由两个小区间转移，所以可以通过枚举中间点
    }
  }
}

显然时间复杂度为 ,空间复杂度为 。

3.2环形 DP

环形 DP 指在一个环上进行，我们可以破环成链（即在后面复制一遍），然后枚举每个 从 到 这个区间进行区间 DP。

for(int x=1;x<=n;++x)
{
  //区间 DP
}

因为相当于区间 DP 做了 遍，所以时间复杂度为 。

4.树形动态规划

其实一开始是想写树形动规才写的这个笔记。

众所周知，在一棵树上，一个点与之相连的点（包括本身）总共分为：父亲，自身，和儿子，在树形动态规划中影响一个点状态的转移/设计也就是由这三者影响，所以树形动归一般是 dfs 实现。

树形 DP 一般可以很清楚的知道状态该从哪里转移，重要的是状态的设计和具体如何转移，一般对于一个点可能会有多个状态，例如典中典之没有上司的舞会就分成了当前点去或不去两种状态，不同状态之间的转换可能是树形 DP 中的难点。

☆4.1 树上背包

树上背包只是把常见的背包放到了树上，其约束一般为在选择了某些点后才能选择一个点（例如：先修和后修），我们可以从前导结点向当前结点连边，背包转移时只能通过其子结点状态进行转移；

设 表示在 结点及其子树中选择 的体积的物品所能获得的最大价值，设 其的子结点之一为 ，则：

最后再考虑自身一定要选，所以：

4.2 树上 DP 经典

• 已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。

• 一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。

• 请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。

这道题很好的体现了树上 DP 的思路，即从父亲，自身和子结点转移。

对于任意一个点，距离小于等于一的点中至少有一个被选择，我们考虑一个点被“覆盖”只有三种情况，自身被选择，父亲被选择，子结点被选择。我们设 分别表示这三种状况所花费的最小值，我们不断 dfs ，在回溯的时候进行更新。仍然设当前结点为 ，其所有子结点为 ，则：

简单解释就是：

• 当选择当前结点，子结点的情况不重要，可以任意从三种中转移，同时最后要加上当前点的花费；

• 当前结点要依赖父结点时，我们不能从其子结点依赖其子结点的父亲（也就是当前结点）的状态转移；

• 当前结点依赖子结点也是同理，只不过我们需要判断不能所有的都选择其子结点依赖其子结点的子结点的状态，因为我们要保证至少有一个子结点是被选择的。

答案即为根结点 的 。

这样就结束了，所以说这道题的状态设计和转移充分体现了树形 DP 的套路。

☆4.3换根 DP

换根 DP 是树形 DP 的一个分支，字面意思就是更改 DP 时的根结点，究其原因是因为不同的点做根结点时的答案不一样，可能会要求你求出每一个或者取和/最大值/最小值等。

较为暴力的思想就是对于每一个根，我们都进行一次 DP ，时间复杂度为 （ 为单次 DP 的时间）。但是在很多时候对于一个点及其子树，它在多个 DP 中的状态是一样的，多次操作会浪费时间复杂度。

具体的操作就是将根结点的一个子结点在根结点上拆下，再将根结点接在子结点上，成为其原来子结点的子结点 ？ ，不断 DFS 处理，回溯时再复原，也就是说换根 DP 的基本形式就是两次 DFS ，时间复杂度得到很大优化。

再具体点，我们在“拆”的时候，相当于要把当前子结点对父结点的贡献减掉，在通过原来的父结点更新子结点，没错，用父亲更新自己（雾）。回溯同理，就是两个点的关系反了过来。

5.状压动态规划

☆5.1 状态压缩

状态压缩即当对于每一个点，我们只有两种可能（一般为选或不选）的时候，如果我们想要记录当前每个点是 0/1 ，我们可以在数组后面多加一维 就可以记录，但如果 过大（但在状压 DP 中最大也不能超过 25，因为一般时间复杂度基于 )，这样就会变得麻烦，所以我们联想到二进制的每一二进制位即非 0 即 1，我们便可以将这些所有 都压缩在一个数中，这个数第 个二进制位便可以表示第 个物品的状态。

由于计算机内部便是二进制实现，所以我们可以使用位运算来方便的解决状压问题（不局限于状压 DP）。（以下二进制位从 1 开始）

5.2 状压 DP

在状压 DP 中，我们总共有 , 中状态，我们通过按顺序枚举每个状态，其一定可以由其前面的状态转移过来，在状压 DP 中，一般会给出限定条件，例如 A 和 B 不能同时选等等，所以可能会出现不合法的状态和不合法地转移；所以在简单的状压 DP 中我们只需要（一般通过位运算）判断是否合法，通过合法地转移，就可以基本解决问题。

后记

花了一天多的时间，感觉确实是自己回忆起来了许多 DP 的套路。

最后还是写一句 CSP2022 RP++。