DP学习记录Ⅰ

· · 个人记录

DP学习记录Ⅱ

前言

状态定义，转移方程，边界处理，这三部分想好了，就问题不大了。重点在状态定义，转移方程是基于状态定义的，边界处理是方便转移方程的开始的。因此最好先在纸上写出自己状态的意义，越详细越好（如至少/恰好，包含/不包含XXX）

DP题通常码量不大，但是非常考验码力，因为细节非常多，比如边界包含不包含0/n?转移顺序是正着转移还是倒着转移？

通常情况下，边界设为 0~n 最为保险，但是要保证不出负数，并且保证0/n+1的状态合法(inf OR -inf OR 0) 等这么写完后发现会越界再改也可以。

至于转移顺序，就要具体分析了。主要看我们想要不想要之前已经转移过来的状态再多次转移 （如01背包就不能一件物品选多次，因此要干净的之前状态；恰好 -> 至少 的常用方法就要用一种类似前/后缀和的思想，就要不干净的/包含所有之前信息的状态来转移。

Continued...

线性dp

通常体现为序列上的dp。应该算dp的基础部分了（尽管也有难题）

P3646 [APIO2015]巴厘岛的雕塑

主要考查的是按位贪心的想法，以及可行性dp转化为最优性dp的方法。妙处在于设置“模板”来确定转移的合法性。坑点在 define int long long 并不能改 1 << i 为 1ll << i，可能爆负数。

可行性dp -> 最优性dp

当我们的一开始想出的状态为 f[i][j][k] 表示前 i 个中某特征为 j，某特征为 k 的状态是否合法的时候，如果 k 越大越好（或者越小越好之类的），可以转化为 f[i][j] 表示前 i 个中某特征为 j，最大的合法的 k 是多少。

背包

常见背包

- 01背包 - 完全背包 - 多重背包（二进制拆分，单调队列，前缀和优化） ### 特殊背包 - 多限制背包 如除了体积外，还有大小，花费等限制。 $f[i][x][y][z][...]$ 表示考虑前 $i$ 个物品，体积为 $x$，大小为 $y$，花费为 $z$...的最大收益。第一位可以压掉。 - 大容量小价值背包 体积的规模巨大，但是能保证价值之和足够小。 $f[i][v]$ 表示考虑前 $i$ 件物品，获得 $v$ 的价值最小要用多大容量的背包。第一位可以压掉，答案可以二分。 ### 背包合并 有 $O(n^2)$ 的做法： 把一个背包看作 $n$ 件物品，即 $f[w] = v$ 看作一个体积为 $w$，价值为 $v$ 的物品。并且要求**只能选择一件物品**。这就要求我们在更新 $F[W]$ 之前，**不能**更新 $F[W - w]$。（具体间转移方程） 转移方程：（$f$ 合并到 $F$ 里） $$MAX(F[W], F[W-w] + f[w])$$ 需要保证 $F[W-w]$ 是干净的，不带任何有关**所有** $f[w]$ 的。因此**需要把 $W$ 放在外层枚举，且倒序； $w$ 放内层，顺序任意**。 ``` for (i = K -> 0) for (j = 0 -> i) MAX(F[i], F[i - j] + f[j]); ``` ### 背包与自然数的划分 把 $n$ 划分为若干不同的正整数的方案数：可以看做对$1$ ~ $n$ 这 $n$ 个物品做01背包。 把 $n$ 划分为若干可重的正整数的方案数：可以看做对$1$ ~ $n$ 这 $n$ 个物品做多重背包。 --- # 树形dp **树形dp做多少题也不算多** - 最大独立集 - 最小点覆盖 - 最小支配(点或邻点被选，谓之“支配”）（三种状态） - 最大匹配 - 换根dp - 基环树dp - 树形背包 ### 换根dp 首先$O(n)$ 的时间内搞出以1为根的信息；再尝试把根换为相邻点，需要 $O(1)$ （或 $O(logn)$)的时间内换完，然后更新答案，递归；回溯时还原信息。 ### 树形背包 树上转移式子为 $f[fa][i + j] = f[fa][i] + f[son][j]$ 的dp题。通常可以通过限制dp上界，保证复杂度不超过 $O(n^2)

这部分细节比较多，对分类讨论能力要求较高。一定要细心啊！！

P3354 [IOI2005]Riv 河流

非常考察费用提前计算思想（没想到就无法dp）。

子树向父亲转移类似两背包合并。 基本转移方程： $$MIN(f[cur][anc][k],f[to][anc][k']+f[cur][anc][k-k'])$$ $$f[cur][anc][k] += (dep[]-dep[]) * w[]$$ > **小技巧1：分类与合并** 我们发现 $i$ 点建与不建伐木场是有一些区别的。因为如果单纯用 $f[i][i][ * ]$ 来表示在 $i$ 点建立伐木场的话，那么 $i$ 的祖先将无法统计上 $i$ 点。 那么我们需要一个 $f[i][anc][ * ]$ 来表示 $i$ 已经建了伐木场了，但是它还是想要在 $anc$ 这一祖先上建伐木场。这样 $anc$ 才能识别并拾取 $i$ 点信息。 因此，我们需要新开一个状态 $g[cur][anc][ * ]$ 表示 $cur$ 点建了伐木场且希望在 $anc$ 处再建一个伐木场。对 $g$ 差别对待，最后再把它合并到 $f$ 里头。 > **小技巧2：无脑赋值初始化** 不知道怎么初始化怎么办？直接拿一绝对合法的转移做初始化即可。 > **小技巧3：费用最后一块算** 如果不愿意在转移里面写那么多 $+w[cur]$ 之类的东西还怕出错算重的话，可以尝试在最后同一加上 $w[cur]$。 ## [P3267 [JLOI2016/SHOI2016]侦察守卫](https://www.luogu.com.cn/problem/P3267) **消防局的设立**的超级加强版。 $f[cur][d]$ 表示从 $cur$ 开始（含）向下 $d$ 层**需要**被覆盖（有可能并不需要，或参差不齐，但是**保证d层往下绝对不需要**）的状态，的最小代价。 $g[cur][d]$ 表示 $cur$ **可以**向上（不含）覆盖 $d$ 层的状态（当然也包含可以向上盖d + XX层的情况），的最小代价。 转移方程： **将新子树的信息逐个加入至原信息中**。 一、g的转移。 0. 初始化（一进dfs，未加入子树时就进行）：$g[cur][d(<= ~ D)] = w[cur]$；$(f[cur][0] =) g[cur][0] = w[cur](if ~ cur ~ is ~ important) ~ OR ~ 0(else)

  1. 子盖外：g[cur][d] <- f[cur][d + 1] + g[to][d + 1]

  2. 外（它子）盖子：g[cur][d] <- g[cur][d] + f[to][d]

  3. 维护“可以”的性质（后缀和）：g[cur][d] <- g[cur][d + 1]

二、f的转移。

  1. 初始化（未加入子树时进行）：f[cur][d] = 0；f[cur][0] = w[cur]~ (if ~ cur ~ is ~ important)

  2. 需要子树全部被盖：f[cur][0] = g[cur][0]

  3. 父子同时等待被盖：f[cur][d] += f[to][d-1]

  4. 维护“d层内随意”性质（前缀和）：f[cur][d] <- f[cur][d - 1]

想清楚所有情况后，转移顺序之类的小细节就有了依据。因此要码这种恶心的DP题，最好先想好所有的状态及转移。

T135128 树

给定 n (<=1e4) 个点的点带权树，要求选择一些点，使得其两两之间距离大于 K (<=1e2)，最大化点权和。

收到上一道题的毒害，我这道题还是想f,g，然后写了五六个式子，最后连定义都弄不清了，发现 f 和 g 有重叠的地方，也就是说，我可以根据 f 来推导出 g。到这里我基本可以确定我又一次掉坑里了。

还是不要思维固化啊

实际上这道题还是听简单的，就只用设计一个状态就好了。毕竟不是覆盖问题。

设 f[cur][j] 表示处理好了 cur 及其子树（目前的），并且子树内（含cur）距离 cur 最近的那个点的距离不小于 j 的...

然后转移方程什么的就很显然了：

f[cur][0] = val[cur] f[cur][min(j, k + 1)] <- f[cur][j] + f[to][k],(j+k+1>K) f[cur][j] <- f[cur][j + 1]

P6223 [COCI 2009] PODJELA

树形背包。

考查状态的灵活改变。使用 f[cur][i] 表示处理完 cur 节点的子树，使用 i 次交换机会的最大 val[cur] 值（贪心)

这里有一个有关dp顺序的小技巧：如果实在不知道怎么安排dp顺序，可以新开一个数组 g，存储 f 的值，然后再清空 f，再用 g 去更新 f，就能保证 g 全部是干净的。

P3177 [HAOI2015]树上染色

树形背包。

考查状态的灵活改变。使用 f[cur][i] 表示处理完 cur 节点的子树，使用了 i 个黑点，子树中的边对答案的贡献的最大值。

注意到，如果存的是子树中的答案的最大值的话，没有“最优子结构”的性质（局部最优 \not= 全局最优).但是如果考虑边的贡献的话，搞完子树里面的边后，只要确定子树中有 i 个黑点，就和外面的边的贡献没关系了。

剩余的和上一道题类似。

其实这种把“两两之间的距离之和”转化为一条条边的贡献还是很常见的一种套路。

P4037 [JSOI2008]魔兽地图

状态不是很好想： f[cur][j][c] 表示 cur 子树中，有恰好 j 个 cur 用来上贡，使用恰好 c 个金币所能获得的最大剩余价值。

然后先算出买 j 个 cur，恰好花 c 个金币的最大剩余价值，这是个树形背包：

g[cur][j][c+c'] <- f[cur][j][c] + f[to][j * need[to]][c']

然后再把 g 处理成 f：

f[cur][j][c] <- f[cur][j'][c] + (j'-j) * val[cur]

叶子的 f 可以直接特判掉：

f[cur][j][j * w[cur]] <- (j'-j) * val[cur]

看似复杂度达到 1e10，但是是可以跑过的。

然后细节较多，各种边界，dp顺序之类的东西要格外注意。

（然而最终竟然挂在了数组大小上...)

P4201 [NOI2008]设计路线

题目要求树上选择一些链，并且要求叶子节点到根节点的“轻边”的数量的最大值最小，还要求方案数。

如果只求最小值，那么这题可以开到 1e6，我们直接贪心DP取最小值即可。但是由于要求方案数，一些“局部不优”的方案可能会被一些不得不做的“更劣解”所“掩盖”掉，使其合法化，因此记录子树最大轻边数并做一些看似不必要的转移显得十分必要。

幸运的是，根据树链剖分的知识可知，最大轻边数是 log 级别的。因此直接计入状态DP即可。

我们可以设 f[cur][k][0/1/2] 表示 cur 子树里轻边数都小于等于 k 的方案数。

为了方便DP，我们可以设 g[cur][k][0/1] 表示 cur 的父边为轻/重边，对父亲关于 k 的转移的贡献

然后分类讨论：

g[cur][k][0]<-f[cur][k-1][0/1/2] g[cur][k][1]<-f[cur][k][0/1] f[cur][k][0]<-f[cur][k][0]* g[to][k][0] f[cur][k][1]<-f[cur][k][0]* g[to][k][1]+f[cur][k][1]* g[to][k][0] f[cur][k][2]<-f[cur][k][1]* g[to][k][1]+f[cur][k][2]* g[to][k][0]

然后随便DP即可。

区间DP

通常是给定一个区间以及某些特征后，该区间内的最优价值/代价就可以通过两个子区间来确定，那么可以考虑通过区间DP来做。

常见的转移方程形式主要为：单点扩展；枚举划分点。

CF1312E Array Shrinking

板子题，不多说。状态：f[l][r] 表示合并 [l, r] 后的那个数是什么。

P3205 [HNOI2010]合唱队

倒过来模拟，发现原前缀体现为一段区间。然后记录 f[l][r][0/1] 表示 [l,r] （最后加在左/右边）的方案数。

注意，如果 f[i][i][0] = f[i][i][1] = 1 的话会算重。可以去掉一个，或者直接将长度为二的状态作为边界。

P1864 [NOI2009]二叉查找树

由于key值一定，可以确定中序序列。

发现区间DP类似BST的构建。一个区间类似一个子树。

如果我们设 f[l][r][rt] 的话，将无法体现 rt 的权值是什么，因为可能已经被修改了。因此，可以设 f[l][r][m] 表示区间的根的权值不低于 m。这样，就可以分两种情况（改 OR 不改）讨论转移。

由于权值可以取实数，避免了很多讨论。

状压DP

有时我们为了完整地表示出状态，不得不用一堆数来表示一个状态。状态压缩是一种常用的方法。

一般状态为01串最方便。如果状态为 k 进制数的话，最好从0开始数数，并且手写几个函数，来支持一系列操作，这样会方便很多。

旅行商（哈密顿路径）

过于经典的状压例题。

逐行转移 & 逐格转移（轮廓线DP）

例题：互不侵犯，炮兵阵地，玉米田

卡逐行转移的例题：P2435 染色

设上一行的状态为 S，枚举这一行的状态为 T。判断 S 能否转移到 T 即可。复杂度: O(nm2^{2m})（一般达不到这个上限，因为有一些不合法的状态；并且那个 m 是位运算复杂度，可以认为是略小于 O(1) 的）

如果 m 比较大，比如 15 或者 20，怎么办？

逐格转移（轮廓线DP）！

（似乎感受到了插头DP的气息）

设 f[state] 为轮廓线上的状态。这样，在转移第 i 行第 j 列的格子转移的时候，只用判断轮廓线上与那个格子相邻的几个格子是否合法即可。

有的时候需要在一行的开头和结尾做一些特判。

复杂度：O(nm2^m)

//P2435
for (register int i = 1; i <= n; ++i)
    for (register int j = 0; j < m; ++j) {
    memcpy(g, f, sizeof(f));
    memset(f, 0, sizeof(f));
        for (register int s = 0; s < All; ++s) {
            if (!g[s])  continue;
            int l = j ? Find(s, j - 1) : -1;
            int u = Find(s, j);
            for (register int t = 0; t < k; ++t)
                if (l != t && u != t)
                    MOD_ADD(f[Add(Del(s, j), j, t)], g[s]);
        }
    }

【经典问题】骨牌覆盖问题：初级 高级 终极

即：给定 n 行 m 列的棋盘，要求使用 1 × 2 的骨牌恰好完全覆盖整个棋盘。求方案数。

感觉hihoCoder上面讲得非常棒

Part1 : n = 2, m <= 1e9

状态 f[n] 表示到 n 列且恰好铺满的方案数。

发现只有最后横铺两个或者竖着铺一个这两种转移。即：f[n] = f[n - 1] + f[n - 2]。矩阵加速求斐波那契数列的第 m 项即可。

Part2 : n <= 7, m <= 1e9

考虑“按行转移”，关键在查询哪些状态的转移是合法的。不难发现，当前行确定后，上一行的可行状态唯一。

如果当前行横铺一个，那么要求上一行对应的那两列为1.

如果当前行竖着来一个，那么要求上一行对应列为0.

如果当前行空着一个格子，那么要求上一行对应列为1.

DFS判定即可。

得到矩阵后，以此作为转移矩阵，随便矩乘几下即可。

复杂度：O((2^n)^3logm)

Part3 : n,m <= 20

数组完全存不下。但是发现每一行对应的只有一种状态，直接存那种状态即可。

复杂度: O(2^nm)

Part4 : 不要求恰好完全覆盖，n,m <= 16

可以考虑按格转移。维护“一行”轮廓线。然后分三种情况转移即可。

Part5 : 不要求恰好完全覆盖，n <= 8, m <= 1e9

这时一种状态就可能会转移出多种状态了。需要 O(2^{2n}) 枚举，O(n) 逐一判断。

据说可以“去掉⽆⽤的状态，即可通过”，然而并不知道哪些状态“无用”。

所以我这种方法只能通过 n <= 7 的点， n = 8 的时候计算量达到了 5e8。不过矩乘常数不大，或许可过？ 可能需要更宽的时限。

P3959 宝藏

由于 n 非常小，因此可以考虑状压。

又因为代价由两个参数决定，如果控制住了其中一个，另一个就可以贪心解决了。

发现 L 没法控制，只好控制 K。即：一层一层地DP。

f[i][S] <= f[i - 1][s] + i * trans[s][S ~ xor ~ s]

需要枚举 S 和其子集 s。

一个常识是：枚举一个集合 S 的所有子集的所有子集的复杂度是 O(3^{|S|})。这个可以用每一个数在各集合中的三种不同状态来证明。同理可证，枚举一个集合 S 的所有子集的所有子集的所有子集的复杂度是 O(4^{|S|}).

然后预处理 trans[s][s'] 后按照层数 DP 即可。预处理 trans[][] 可以贪心。思想与斯坦纳树类似。

复杂度： O(n^23^n)

P4297 [NOI2006]网络收费

DP综合题：需要用到树形DP，背包，状压DP，以及“做承诺”（费用提前计算）思想。

设f[cur][k][s] 表示DP到了cur，子树中共有 k 个 B 型点，且从 fa[cur] 到根的点的状态为 s 的最优代价。

叶子的所有状态可以直接处理出来。这里包含了所有代价，剩下我们要做的只是把子树拼一拼，看看合不合法。

根据 A 型点的子树 A 严格少于 B 型点，我们控制枚举的 k 的范围。对于“拼子树”，做树形背包即可。

然后发现需要 O(2^{3n}) 的空间复杂度。考虑到深度变浅一点， |s| 会变小一点，k 会增大一点。这样，我们直接把后两维压成一维即可做到空间 O(2^{2n})。

细节非常多。我谨慎小心地写代码，还出了六个错。还是太菜了。