【总结】DP 特训总结

PhainonK · 2024-11-11 20:56:01 · 个人记录

老师让我们一人推荐一道 dp 题目，组成一个 DP 特训。
我的题目是临时抓的。所以就在 CF 题库里随便拉了一道。好像太水了。

A

一个我没有见过的 trick（或者说见过但想不起来了）。

分析题意，记录袋鼠每次到达的位置，可以简化成要求构造一个序列，对于一个 a_i(1<i<n)，须满足 a_i>a_{i-1},a_{i-2} 或 a_i<a_{i-1},a_{i-2}。

显然直接 dp 是不好做的。而且由于是一个排列，还要考虑元素是否重复的问题。按照顺序去 dp 完全做不了。

可以把数字之间的关系转化成图形，不难发现，其实序列是一个波浪形的。要么大于两边的数，要么小于。但是这样仍然不够简单，所以可以转换一下 dp 的顺序。

考虑不按照序列的先后顺序 dp，而是按顺序加入数字，从小到大。这样，每次加入的数字一定大于前面的所有数字，加入时一定是大于两边的。并且也限定了加入的方式：要么自成一段，要么就合并两段。不能加在一段的一端是因为，后面加进来的数都大于当前这个数，对于这个数就无法满足所谓“波浪形”了。

所以，每一次的操作相当于在序列中插入一个数。这个就是插入 dp。

所以设一个 dp 状态 dp_{i,j} 表示，当前加入了 1\sim i 这些数字，一共有 j 段的方案数。

每次插入一个数，可以单独成一段，可以合并两段。注意如果是起点或终点则只能放在序列两端，特殊转移一下即可。

非常巧妙的一道好题。

这个 trick 被评价为，没见过，怎么也做不出来；但是见过之后，如果能够理解并记住，下次遇到就是水题了。

要记住这个 trick。

当然，在做题之前，包括这道题也要考虑，插入的方式会不会算重。

B

这道题目还是挺有意思的。之前做过。
没记错的话是在最后一场选拔考试的前一晚，在洛谷上搜哈利波特搜出来的。

首先考虑贪心或者直接 dp 这类的做法，但可以发现不好做。因为每一次的决策并不知道对方下一次去哪里，就变成了一个更像博弈的游戏，不好做。但是如果转成判定性问题可能会更好考虑。

所以可以二分一个 k，每次判定是否可行。

这道题目最妙的地方在于状态设计。

首先，这道题目从上往下考虑是不好考虑的。从一个点往下走，可以走到任意一个儿子。在对手走出这一步前，实际上我们不知道该先染那些位置。

但是如果从下往上考虑，对于一个点考虑从它的子树转移过来，而这个点本身也只能转移到父亲去，可算的路径就唯一了。

然后考虑怎样算代价。对于一个点，当前对手要再走一步，显然这个点所有的儿子是必须要染的。而在某一些点，当它的儿子数量不足 k 个时，还剩下一些操作次数。当儿子数量多于 k 个时，又需要更多的操作数。所以不难想到，在前面有剩余操作时，把这些操作用到后面不够的地方，就可以保证不输了。

相当于，在一个点操作时，就要考虑它的子树中需要被帮助的点。这个用 dp 是很好算的。

但是，如上文提到的，我们并不能预测对手会走到那个子树，所以代价计算的方法不是对于所有取最大值或最小值，而是求和。

令 dp_u 表示子树 u 想要保证对手走到这个点时，一定不会输，需要多少次来自祖先的帮助，也就是提前染色。

转移方程：dp_u=\max\{ \sum_{v\in son_u}dp_v+1-k,0\}。

本次 check 合法的条件即为 dp_1=0。

比较巧妙的状态设计。当时第一次做的时候也不会，想了很久，看了题解恍然大悟了。还有，这种类似博弈的问题，直接做不好考虑，可以想到转换成判定性问题去做。

C

这道题目讲完后看，也不算难。并没有什么很新的东西。

对于求一条路径的代价，有两个考虑的方向：

• 在两个端点的 lca 处求贡献。
• 使用换根转换成根到一个点的贡献。

这道题两种方法都可以用。最后补的是在 lca 处求价值的做法。

其实解法没有什么好讲的，没有特别有亮点的地方。

这道题目主要是细节比较多，加上有一个需要注意的点：走一条路径的方向会使价值不同，所以要分别记录从当前点向下走，和从子树走上来到这个点两种状态的值，转移方程也略有区别。

最后在统计答案的时候，需要将两种状态拼起来。这里有两个点：

• 树上背包复杂度是 O(nk)。
• 因为路径不能重复，可以这样做：遍历到当前儿子，先用此儿子的 dp 值和之前求得的当前点的 dp 值合成答案，然后再更新当前点的 dp 值。

D

对于这道题，主要在于两个方面：

• 找性质。
• 状态设计。

且二者关系是先找到了性质，才可以设出状态。

对于这道题，首先需要发现一些性质。

有一个显然的性质：如果一盏灯的照亮范围完全包含了另一盏灯，那么改变另一盏灯的朝向，新方案一定不会劣于旧方案。

若这道题从左向右考虑，最理想的情况一定是所有灯朝向右，尽量覆盖远的区域。但是这样做会导致中间或许有一些空隙没有被照亮，所以需要一些灯朝左“补救”。当一盏灯朝左（即不得不朝左），若其覆盖的范围内有灯也朝左，且此灯的照亮范围被完全包含，根据上面的性质，就可以改变让其朝右。

有了这个关键、但其实并不难的性质，本题就可以做了。

具体做法不再细讲，还有一个关键点：

• 虽然题目求的是是否可行，但是状态不一定要问什么求什么。有时求的答案比较简单，dp 数组所表示的值也可以作为转移可行性的一部分。

例如本题最后的转态是：设 dp_i 表示前 i 盏灯能够点亮的最长前缀。

根据前文所述性质，这个状态的意义就在于，由于这个最长前缀的后一位没有被点亮，所有需要有后面的灯朝左覆盖这个位置。

对 i 进行转移时，就可以找到一个最小的 j 满足前 j 盏灯可以覆盖到前缀 i-p_i-1，然后让第 j+1\sim i-1 盏灯都朝向右，得到状态 i 可以覆盖到的最长前缀。

还有一个点：

• 二分在 dp 中的作用不止转成判定问题，决策点满足单调性的时候可以二分找。

E

还是插入 dp。

与 A 的思路有一定相似性，都是需要不重，所以考虑按顺序加入数字。不过这道题需要考虑的限制就多多了。

矩阵加速 dp 有待复习。

F

冗余的 dp 状态可以优化。

G

太水了，被秒了。

不过也有一些小提示：

• 决策单调性，尤其斜率优化，需要常复习。一段时间不做，下次遇到可能就又陌生不会了。
• 一些单调性的证明可以画图。不过本题证明本身就十分简单。复杂的证明如果在赛场上遇到，个人认为可以造随机数据验证，然后先放一边，去做做别的题。在 OI 赛场上去搞严谨证明肯定是迫不得已的情况下才会做的事情。

H

这种计数还带容斥的题目真的不太会做。

按照思路中的关键点分点谈：

• 要求拿到不同颜色的糖果的方案数，但糖果编号不同就是不同的方案。显然这一个限制没什么用，因为颜色不同，所以不可能拿到和原来一样的糖果，同种颜色的糖果是等价的。方案数最后除以每种颜色个数的阶乘的乘积去重即可。对于这种实际上等价的东西另外处理会方便的多。 这样，后面就可以不按编号而是按颜色考虑。
• 计算糖果不重的方案数显然不好计算。所以可以考虑计算有重复的方案数，用总方案数减去即可。
• 可以轻易得出状态为 dp_{i,j} 表示前 i 种颜色，有 j 个人拿到相同颜色的方案数。但是发现，无论是相同还是不相同，都无法做到无后效性的转移。因为状态中无法记录前面已经分配了哪些糖果。
• 本身这个状态的意义是用所有方案分别减去重复了不同个数的方案数，要求每一个 f_{n,i} 是不重的。但这一点无法做到。所以不妨允许重复，方案数使用容斥计算。 所以具体做法就是只计算相同的数，不相同就不算。最后对于一个 f_{n,i} 直接乘上 (n-i)!。

最后再容斥一下，还有第一步的去重即可。

这道题给我的一个启发是：

• 去考虑在什么情况下才需要使用容斥。

我们应该通过题目的特性去判断到底该采用什么样的方法，而不是看到计数题就刚容斥，也不是看到 2^n 疑似能过就直接上容斥。或许这些做法有一定的帮助，但是更重要的是一步一步地推导，到了某个地方，朴素的去重进行不下去时，发现容斥是可做的。

例如本题，只考虑简单的重复，要求各终点状态的方案数不重，求解这个问题的难度不亚于直接求原问题。并且可以发现最大的困难正在于保证不重这一点。加以分析得出容斥可以解决这个问题。

而对于有些题目，容斥的做法会使问题变得更加复杂甚至不可做。

所以这启示我，还需要多做题，多感受，去体会在什么场景下使用容斥，什么场景下使用别的方法，是去重容易，还是直接设出保证不重的状态容易。

I

单调队列水题。代码细节有点多。

我得到的启发是：

• 如果我写单调队列题，一定要先把 O(n^2) 的代码给写出来，再优化成单调队列。一个是因为这样更加清楚，需要优化哪些地方；一个是因为方便对拍。无论是为了调试还是验证代码是否正确。毕竟我对自己一次写对单调队列题毫无信心。

J

水计数。双指针。

启发：

• 区间分段，要求某信息相同的问题，可以尝试想想有没有区间信息必须等于全局信息的性质。类似的之前模拟赛有一道题目也有这个性质（虽然不是 dp 题）。

K

一道没人想做的原题。

技巧：

• 对于有环的 dp 转移，可以使用图论算法。

L

很有意思的题目。

但是真的是 dp 吗？

首先，对于给出的 top 值，可以把这些点划分成一些链。而我们要做的就是把链都拼在一起，求方案数。

首先，出现次数最多的一定是根。考虑怎么拼在一起。

一个简单的想法，拼链的时候，如果要拼在原来的链中间，如果当前这条链加上中间往上的部分长度比原来的链还大，根据长链剖分的操作，这应该是一条新的更长的链，就不符合要求了。

为了规避这种情况，对于链按照长度排序，从大到小依次做事没有问题的。

然后再根据上述思路考虑就很简单了。

当新的这一条链拼接在原有的一条链上，可以选择的连接位置有要求，即拼接位置到链头的长度加上新链的长度须小于等于原链的长度。很好理解，如果大于，链头到连接点，加上新链会是一条更长的长链。

对这个计数就可以了，也十分的简单。

式子不想写了，直接看代码吧。

s[0]=1;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),cnt[a[i]]++,s[i]=1ll*s[i-1]*i%mod;
sort(cnt+1,cnt+1+n);
int sum=cnt[n],ans=s[cnt[n]-1];
for(int i=n-1;i>=1;i--){
    if(!cnt[i]) break;
    ans=1ll*ans*s[cnt[i]-1]%mod*(sum-1ll*(n-i)*cnt[i]%mod+mod)%mod;
    sum+=cnt[i];
}
printf("%d\n",ans);

这道题目虽然和 dp 好像没太有什么关系，但是有一个技巧同样适用于 dp：

• 当很难设状态或者很难转移的时候，可以考虑换一换转移的顺序。或许会使操作简单很多（A 题和本题都有这样的特点）。

M

很难的一道题。

• 对于一个限制，可以把大小关系转化为一段前缀的要求。
• 特定的 dp 转移式可以转化成差分。

总结

一些启发和技巧都在上文，不再赘述。

通过这次 dp 特训学习到了很多技巧和 trick，也看到了这个对于我来说非常薄弱的板块的一些提升方法和方向。

大家其实手里都有很多好题。我这一次的准备比较匆忙，也说明平常或许没有足够的主动性和自己规划安排的能力，没有针对自己的弱项去训练。

这些问题有待改进。