Codeforces DP训练

813D：

题意：给出长度为$n$的序列，从中找出$2$个子序列，满足每个子序列相邻两数之间要么相差$1$，要么同余于$7$，求这两个子序列的最长长度和。
题解：DP优化主要考虑状态的减少和转移的加快，这个题$f[i][j]$表示分别以$i$、$j$为结尾的子序列最长长度和的状态不能减少，考虑优化转移。防止一个位置被重复选择，要强制限制$i<j$，那么固定$i$，$f[i][j]$实际上是从前面的某个$f[i][k]$转移过来，所以可以通过维护$mx1[p]$、$mx2[p]$表示$a[k]\%7=p$的最大$f[i][k]$和$a[k]=p$的最大$f[i][k]$，即可实现$O(1)$转移。

796E：

题意：有$n$道题目，有两个人分别会做某些题目，有$p$次偷看机会，每次可以偷看某个人最多连续$k$道题目，求最多偷看几道题目。
题解：$f[i][j][x][y]$表示前$i$道题目，用了$j$次偷看机会，第一个人还可以看$x$道，第二个人还可以看$y$道即可。

534F：

题意：一个只有黑白格子的矩形，给出每行每列的连续的黑色格子段数，还原出这个矩形。
题解：比较简单的一道题目，但是还是卡了卡。首先状态压缩DP很好想，就一列一列填就行了，但是这个做法TLE了，原因是状态数太多，一个状态能被很多个状态转移到，所以考虑倒着来，做记忆化搜索就行了，因为这样找到一个合法的就会结束了。

946G：

题意：给出$n$个数，问最少把多少个数改成任意整数后，使得之后的$n$个数能通过去掉一个数，成为一个严格上升序列。
题解：套路都忘光了……如果最后要求的是一个不降序列，问题就简单了，那么我们就通过每个位置$-i$实现这一转化。然后对于删数这个操作，实际上是使被删数后面的数由$-i$变成$-(i-1)$，用两个DP数组分别维护删了数和没删数的最长不降序列即可。

856C：

题意：给出$n$个数，把这$n$个数拼起来成为一个数，求$n!$种方法中有多少是$11$的倍数。
题解：首先有性质：一个数奇数位数上的和与偶数位数上的和的差的绝对值为$11$的倍数，这个数即为$11$的倍数。对于每个数，它原来的奇数位和偶数位可能会在最后的答案中倒过来，易得若$n$个中有$m$个奇数位数的数，那么有$\lfloor \frac{m}{2}\rfloor$个奇数的贡献是要倒过来的，偶数位数的数的贡献则可以任意，那么分别对奇数位数的数和偶数位数的数DP一下，$f[i][j][k]$表示前$i$个有$j$个贡献反过来，余数为$k$的方案数即可，最后把偶数插进奇数中。

178F2：

题意：给出$n$个字符串，选出其中恰好$k$个组成一个集合，定义集合的权值为字符串两两之间最长公共前缀之和，求权值最大值。
题解：建出字典树的虚树，在上面DP即可。

946F：

题意：定义$F(x)$表示一个$01$串，$F(0)=0$，$F(1)=1$，$F(x)=F(x-1)+F(x-2)(x>1)$，$+$表示字符串的拼接，给出一个$01$串，求其在$F(x)$的所有子序列中的出现次数之和。
题解：字符串匹配可以考虑区间DP，$f[i][l][r]$表示$s[l-r]$在$F(i)$的所有子序列中的出现次数之和，分情况讨论转移即可。

958C3：

题意：给出$n$个数，把他划分成恰好$k$段，求每段的和$\%p$之和的最小值。
题解：暴力DP：$f[i][j]$表示前$i$个数划分成了$j$段，$f[i][j]=\min \{f[k][j-1]+(sum[i]-sum[k]+p)\%p\}$，可以按照$sum[i]$与$sum[k]$的大小关系分类讨论，用数据结构优化，但是还不够，可以对于每个余数维护最小值，再用数据结构维护，那么$logn$变为$logp$，可以通过。

875E：

题意：有两个快递员$A$，$B$，他们的初始坐标为$s1$，$s2$，有$n$个需要送的地点坐标为$a_{1...n}$，按照派送优先顺序编号。求两个快递员派送过程中相隔最大距离的最小值。
题解：二分答案，考虑如何检验。从前面开始不会搞，倒过来搞。这样我们不需要知道谁在送货，只需要维护当其中一人在$a_i$时，另外一个人的区间即可。

643E：

题意：一开始有只有根节点，支持两种操作：1、插入一个节点，以当前某节点为父亲。2、询问以某个节点为根的子树，若每条边有$\frac{1}{2}$的概率断掉，期望的最大深度是多少（在误差范围内即可）。
题解：首先很重要的一点，若深度太大，那么概率就会小的可以忽略不计，所以实际有用的层数不会太多，这应该是概率DP中不错的套路。那么直接$f[i][j]$表示以$i$为根节点，最大深度为$j$的概率即可。

888F：

题意：给出$1$到$n$的点两两之间的边是否可以连，求连成一棵树且不存在两条边$(u_i,v_i)$、$(u_j,v_j)$满足$u_i<u_j<v_i<v_j$的方案数。
题解：直接$f[i][j]$表示把$i$到$j$连起来，且$i$和$j$必须有边相连方案数，$g[i][j]$表示把$i$到$j$连起来方案数，互相转移即可。

1034C：

题意：给定一棵树，每个点有一个点权$a_i$。整棵树是第$1$级划分。定义第$i$级划分是将第$i-1$级划分中的每个区域划分成至少两个新的区域，并且所有区域都是一个连通块，每个点在每一级中只属于一个区域，在同一级划分内每个区域内的点的点权和相等。一种划分方案包含它划分的每一级。两种划分方案不同当且仅当它们划分的级数不同，或者存在一个点在某一级中它们在两种划分方案中属于不同区域。
题解：感觉这个题跟之前的某个把树划分成若干个点数相同的块有点类似，策略是一样的，若每块的点权和是$k$，那么当某棵子树权值和达到$k$时就砍掉这棵子树，所以对于每个$k$都只有一种方案划分。$f[i]$表示子树权值和$s[x]\%(s[1]/i)=0$的$x$有多少个，然后再用$ans[i]$表示最后分成$i$块的方案数即可。关键是如何求$f[i]$。暴力是$O(n^2)$的，考虑求出对于每棵子树最小合法的$i$，这样有且仅有任意正整数倍的$i$都是合法的，那么这个$i$显然会$s[1]/\gcd (s[1],s[x])$（这题比较难啊）。

708E：

题意：（最好结合图理解）每天除上下两排，最左边和最右边的每个方块都有概率消失，求最后这个图形连成一块的概率。
题解：比较简单的DP是这样的：$f[i][l][r]$表示到第$i$行，剩下了$[l,r]$的方块的概率，转移可以用前缀和优化做到$O(1)$，但是这样光是状态就是$n^3$的，没有前途。我们最后要求的是${\sum }_{l=1}^m{\sum }_{r=l}^{m}f[n][l][r]$，考虑直接DP某个前缀和，不求$f$，那么这样就可以做到$O(nm)$，也是个不错的优化方法吧。

886E：

题意：求$n$的排列有多少满足：从左到右扫求最大值，当最大值不再变化$k$次后的最大值不为$n$。
题解：计数题还是不会啊，也不太会思考，只能多做了。$f[i]$表示$i$个数，最大数放在最后的合法方案数。转移就考虑次大数放的位置即可。

908G：

题意：定义$S(x)$为$x$的各个位数字从小到大排形成的数，前导$0$忽略，如$S(321)=123$，$S(1002)=12$，求${\sum }_{i=1}^{n}S(i)$。
题解：考虑计算每个数字的贡献，比如$3\times 10^n$，我们这样计算：在第$n$位填$1、2、3$的时候分别加上$10^n$的贡献，那么每个数字的贡献就是最后大于等于它的数字个数，如果有$k$个，那么这个贡献就是$\frac{10^k-1}{9}$，也就是$k$个$1$，那么直接数位DP就行了。

367E：

题意：求选出$n$个区间$[l_1,r_1]....[l_n,r_n]$，使得所有$1<=l_i<=r_i<=m$，且区间之间没有包含关系，至少有一个区间左端点为$x$的方案数。
题解：$f[i][j][k]$表示到了第$i$个数，左端点有$j$个，右端点有$k$个的方案数，那么一个数可以分四种情况转移。对于这种二元组的题，不一定要一组一组取，还要考虑一个一个取。

436D：

题意：无限长的数轴，上面放着$n$个布丁，相邻两个布丁会黏在一起，移动任意一块另外一块也会移动，每次你可以向左或向右移动一块布丁，这块布丁会一直运动到撞到一块布丁为止，然后他们就黏在一起了，数轴上有$m$个特殊点，你可以做无数次操作，求最多能覆盖多少个特殊点。
题解：$f[i]$表示前$i$个布丁最多覆盖点数，$g[i]$表示部分靠到$i$的情况下最多覆盖点数，直接DP即可。

1055E：

题意：给出一个序列和一些线段，要求恰好选出$m$条线段覆盖序列，求被覆盖数从小到大排序后第$k$个的最小值。
题解：简单二分DP。

58E：

题意：给一个算式，要求加上尽量少的数字使等式成立。
题解：直接DP可以，但是写成dfs要更简洁一点，以后要注意什么时候写dfs。

954H：

题意：给一棵树，第$i$层的每个点儿子数都相同，求长度为$k$的简单路径数。
题解：比较简单的计数题，预处理出$f_{i,j}$表示到第$i$层的一个点长度为$j$的方案数，然后枚举起点计数即可。

382E：

题意：求满足$1$号点度数不超过$2$，其它点度数不超过$3$、最大匹配数为$k$的无根树数目。
题解：把$1$看做根节点，就是求最大匹配为$k$的二叉树个数，$f_{i,j,0/1}$表示大小为$i$，最大匹配为$j$，根是否被匹配的方案数即可。

938F：

题意：给一个字符串，第$i$次删除长度为$2^{i-1}$的一个子串，删到不能删为止，求最后字典序最小的字符串是什么。
题解：显然先后顺序是没有影响的，考虑一位一位确定，$f_{S,i}$表示用了集合$S$的操作，保证前$i-1$位最小，第$i$位最小是原串中的第几位，每次枚举用哪种操作转移即可。

917C：

题意：有$n$个石头，前$x$个石头上各有一只蝌蚪，每次最左边的蝌蚪会跳到右边某个没有蝌蚪的石头上，每次最多跳$k$，一次跳不同距离消耗不同的能量，跳到一些特殊石头上会消耗或者获得一定能量，求全部跳到后$x$个石头最小消耗能量。
题解：思维有点僵化了，这种取$\min$的也是可以矩阵乘法的，$k$较小，可以状压，$f_{i,S}$表示从$i$开始的$k$个石头是否有蝌蚪的状态为$S$的最小消耗，但是这样有个问题，$i$不一定会转移到$i+1$，因为$i$可能没有蝌蚪，此时要令形如$0110$这样的状态先转移到$1100$，这样保证最左边一定有蝌蚪再转移，这样就能够保证转移可以矩阵乘法。

755G：

题意：有$n$个不同的球，选出若干份，每份要么是相邻的两球，要么是单独一个球，允许有球不在任何一份，但不允许球同时出现在两份中。求选出$1$~$k$份的方案数。
题解：$f_{i,j}$表示前$i$个球选了$j$份方案数，那么$f_{i,j}=f_{i-1,j-1}+f_{i-2,j-1}+f_{i-1,j}$，考虑优化，无法矩阵乘法，多项式看上去也不行。倍增一下，$f_{2i,j}={\sum }_{k=0}^j{f}_{i,k}\times f_{i,j-k}$，还有中间两球组成一份，加上${\sum }_{k=0}^{j-1}{f}_{i-1,k}\times f_{i-1,j-1-k}$。这样的话我们发现，只需要维护$f_i、f_{i-1}、f_{i-2}$就行了，直接上NTT，要注意$k$以后的项一定要清零！