[TOC]

早有打算做点$dp$题，今天恰好看到gyh写了一个DP从入土到入门，那就硬抄呗（狗头

线性DP

顾名思义，就是在线性状态上进行递推
常见在序列上对区间操作的问题，如区间合并

P4910 帕秋莉的手环

P4910 帕秋莉的手环

给定一个有$n$个位置的环，每个位置可以填入$1/0$，要求不能有相邻的$1$

多组数据$T\leq 10,n\leq 10^{18}$

• $20pts$

暴力枚举

• $60pts$

$f[i][0/1]$表示第$i$个位置是$0/1$的方案数

$\begin{array}{l} \left\{\begin{matrix} f[i][1]=f[i-1][0]\\f[i][0]=f[i-1][1]+f[i-1][0]\end{matrix}\right.\end{array}$

复杂度为$O(Tn)$,期望得分$60pts$

• $100pts$

考虑矩阵优化

$\begin{bmatrix}f_{i-1,0}&f_{i-1,1}\end{bmatrix} \times \begin{bmatrix}1&1\\1&0\end{bmatrix} = \begin{bmatrix}f_{i,0}&f_{i,1}\end{bmatrix}$

复杂度为$O(Tlogn)$期望得分$100pts$

代码见P4910 帕秋莉的手环

P4933 大师

P4933 大师

给定$n$个建筑，第$i$高度为$h[i]$，求拆掉某些建筑后剩下的是等差数列的方案数(对$998244353$取模)

$n\le 1000,h_{max}\le 20000$

• $30pts$

枚举每个建筑拆不拆

复杂度为$O(2^{n}*n)$,期望得分$30$

• $60pts$

枚举等差数列的公差，然后每次扫一下整个序列，看看能否满足，$h_{max}\le2000$

上面的是错误的算法，我傻了

但是我们注意到值域$h_{max}\le 2000$，其实是很小的

大胆猜测枚举公差的方向肯定没错，淦

用$f[i][j]$表示以$i$结尾，公差为$j$的等差数列有多少个

每次枚举一个小于$i$的位置$k$，让$k$的高度满足$h[k]=h[i]-j$，然后用$f[k][j]$更新$f[i][j]$

复杂度为$O(n^2*h_{max})$，期望得分$60$

• 真$100pts$

考虑优化$60pts$

等差数列任意相邻两个数的公差是一定的

我们没必要去枚举公差，直接后面的减去前的就得出来公差了，$qwq$

$f[i][h_i-h_k]=\sum\limits_{k<i}f[k][h[i]-h[k]]+1$

复杂度为$O(n^2)$，期望得分$100$

代码见P4933 大师

P3847 调整队形

P3847 调整队形

给定长为$n$的颜色序列，颜色为$1$到$n$，问最少经过多少次操作能让颜色序列左右对称

操作有添加，删除，插入，替换颜色

$n \le 3000$

仔细分析题目题解可以发现：

• 在队伍中任两个人中间插入一个人（衣服颜色依要求而定）
• 剔掉一个人

这两个操作是没必要的，因为插入一个人的状态一定包含在加入一个人的状态里面，同理剔除一人和加入一个人等效

所有我们就只需要处理加入一个人和换颜色即可

$f[i][j]$表示$i$到$j$对称需要的最小操作次数

• 加入一个人

$f[i][j]=\min(\min(f[i][j-1]+1,f[i+1][j]+1),f[i][j])$

• 换颜色

$f[i][j]=\min(f[i+1][j-1],f[i][j])$

代码见P3847 调整队形

P4170 涂色

P4170 涂色

给定一个长为$n$的序列，每次可以把一段涂成某种颜色，后涂的会覆盖先涂的，问最少涂几次能得到目标状态

$n\le50$

和上面拿到题目类似
设$f[i][j]$表示$i$到$j$最少的涂色数量
分情况讨论
$i=j$时，显然有$f[i][j]=1$
$i\neq j$时

• 如果$a[i] = a[j]$，就继承一下上一次涂的色，$f[i][j]=\min(f[i+1][j],f[i][j-1])$
• 如果$a[i]\neq a[j]$，就把颜色看成两段，枚举分割点$k$，$f[i][j]=\min(f[i][k]+f[k+1][j])$

代码见P4170 涂色

P3146 248 G

P3146 248 G

给定一个$1*n$的地图，在里面玩$2048$，每次可以让相邻的两个相同的数$x$合并成$x+1$，问最大能合出多少。

$1\leq x \leq40$

这种合并操作基本就是区间$DP$(狗头

设$f[i][j]$表示$i$到$j$合并的最大值（区间$DP$经典状态）

则显然转移方程就是$f[i][j]=\max(f[i][j],f[i][k]+1),k\in[l,r),f[i][k]=f[k+1][j]$

这样就可以水过本题了，当时其实这样是错误的

$Hack$数据：

Input：

8 2 1 1 2 4 2 3 4

Output：

4

如果$f[i][k]=f[k+1][j]=0$的话，按照上述转移方程得到的$f[i][j]=1$，就错了

$f[i][j]=\max(f[i][j],f[i][k]+1),k\in[l,r),f[i][k]=f[k+1][j]>0$

代码见P3146 248 G

P5774 病毒感染

P5774 病毒感染

有$n$个小镇，每个小镇$a_i$个人感染了病毒，$JYY$每到一个村庄可以选择救治该村所有的人(这一天没有人死亡)，或者去下一个村庄，当他已经跳过一个村庄后再向该村庄走时(此处不明白请仔细看题目中绝对值的关系那个地方)，必须来救治该村庄

第$i$个村假设有$a_i$个人感染，那么第二天这$a_i$个人会死亡且会新感染$a_i$个人，求最小死亡数

$1\le n\le3000,1\le a_i\le10^9$

这题真的是普及+/提高吗？

• $50pts$

定义$f[i]$为治愈前$i$个村庄的最小死亡数

对于每个村庄来说$JYY$可以选择治疗还是不治疗，重点在于怎么处理回去这的问题

由题目中$|k-i|<|k-j|$可得只要想从$j$回去治疗$k$，那就必须把之前的全都治了

所以我们只需要枚举$k$即可实现转移

复杂度$O(n^3)$，期望得分：$50$

• $100pts$

上面的做法时间主要浪费在计算略过村庄再回来的死亡人数上，我们可以考虑预处理这一部分

定义$g[i][j]$表示从$i$到$j$在回到$i$的最少死亡人数

但是我不知道$g[i][j]$应该怎么转移(看不懂题解)，先挖个坑，以后回来写完

回来填坑了

枚举$i$为起点，$j$为长度，$sum[i]=\sum\limits_{k=1}^{i}a[k]$

$g[j][i+j]=g[j+1][i+j]+\min((sum[i+j]-sum[j])*2,a[j]*i*3+sum[i+j]-sum[j])$

则设$f[i]$为前$i$个村庄消灭疫情最小死亡人数

$f[i]=\min(f[j]+g[j+1][i]+(4*i-4*j-2)*(sum[n]-sum[i]))$

淦，这转移真恶心，如果看不懂请点这里

代码见P5774 病毒感染

P2501 [HAOI2006]数字序列

P2501 [HAOI2006]数字序列

给定一个$n$个数的序列，问最少改变多少个数能让它变成一个单调严格上升的序列，且让每个数改变的绝对值之和最小，输出个数和最小值

$1\le n\le3.5*10^4,1\le a_i\le 10^5$

• $Problem\ 1$

看懂题目之后，淦，这什么东西啊

我陷入了满足的数应该被改变的思考中......嗯，想不出来

正着想不出来可以反着想，考虑满足什么条件的数应该被保留

如果$a[i]$和$a[j]$之间的数本身合法或者能被改成合法的那么它们就是应该被保留的

容易得出满足$a[j]-a[i]\ge j-i$

即$a[j]-j\ge a[i]-i$

显然，可以令$b[i]=a[i]-i$，然后求$b$的最大不下降子序列(因为条件是$\ge$)的长度$len$，$n-len$即为第一问答案

• $Problem\ 2$

我们继续在$b$上考虑，对于一对被保留的点$b[i]$和$b[j]$，他们之间的数一定都是不合法

现在的问题就在于如何把这些数都改变才能使改变量最小

一个结论

设分界点为$k$，则对于左边$b[l] \to b[i],l\in[i,k]$对于右边$b[r]\to b[j],r\in [k+1,j]$

证明的话就不写了，我也不会

设$g[i]$表示$[1,i]$的在改变次数最小时最小改变量之和

$g[i]=\min(g[j]+w(j+1,i))$

根据上面的结论可以通过前缀和和后缀和来优化求$w(j+1,i)$的过程

复杂度为$O(n^2+nlogn)=O(n^2)$，期望得分：$100$

代码见P2501 [HAOI2006]数字序列

P5301 [GXOI/GZOI2019]宝牌一大堆

P5301 [GXOI/GZOI2019]宝牌一大堆

不简化了，太长了

做的第一道NOI/NOI+/CTSC的$DP$，做这个题要时刻记得各种牌是怎么组成的,$qwq$

雀魂大毒瘤，麻将已无爱

• 七对子

直接贪心选择权值最高的七个即可

• 国士无双

暴力枚举，$O(13^2)$

• $3*4+2$

设$f[i][j][k][a][b][c]$表示枚举到第$i$张牌，已经有了$j$张面子，有有$k$对雀头也可，第$i$种牌用了$a$张，第$i+1$种用了$b$张,第$i+3$种用了$c$张的最大分数，或者$k=0/1$

然后枚举转移即可

• 性质$1$

经过艰难的读题后可以发现杠子是不需要考虑的，因为杠子的价值$C_4^{4}=1$就算是宝牌也没有刻子的高$C_4^{3}=4$

• 性质$2$

三个刻顺子是没有三个刻子更优的，所有对于$l,m$只需要枚举到$2$就行了

• 性质$3$

$f$值是$0$的话说明不合法直接退出即可

• 转移方程

$f[i][j][1][k+2][l][m]=max(f[i][j][1][k+2][l][m],\frac{f[i][j][0][k][l][m]}{C_{a[i]}^k}*C_{a[i]}^{k+2}*dora[i]^2)$

$f[i][j+1][o][k+3][l][m]=max(f[i][j+1][o][k+3][l][m],\frac{f[i][j][o][k][l][m]}{C_{a[i]}^k}*C_{a[i]}^{k+3}*dora[i]^3)$

$f[i][j+1][o][k+1][l+1][m+1]=\max(f[i][j+1][o][k+1][l+1][m+1],\frac{f[i][j][o][k][l][m]}{c_{a[i]}^k}*c_{a[i]}^{k+1}*\frac{dora[i]}{c_{a[i+1]}^l}*c_{a[i+1]}^{l+1}*\frac{dora[i+1]}{c_{a[i+2]}^m}*c_{a[i+2]}^{m+1}*dora[i+2])$

• 注意

注意在转移之前判断合法不合法（剩的牌够不够），开long long
为什么要开$O2$才能过？我吧我忘记判断不合法状态了，$qwq$

复杂度为$O(34*4*4*2*2)=O(2176)$，期望得分：$100$

代码见P5301 [GXOI/GZOI2019]宝牌一大堆

状压 DP

顾名思义，就是通过二进制压缩，将状态转化为一个数，用这个数作为动态规划的状态进行 $DP$

常见于某些数据范围较小的题目，如$n\le32$,$n\le 64$等

P3622 [APIO2007]动物园

P3622 [APIO2007]动物

给定一个有$n$个动物的环，你可以移除某些动物，有$c$个小朋友，每个小朋友能看到$5$个动物，每个小朋友有喜欢的和不喜欢的动物

定义小朋友高兴为

• 至少看到他喜欢的一个动物
• 至少有一个他不喜欢的动物被移除

问最多有多少小朋友高兴

$10\le n \le10^4,1\le c\le5*10^5$

每个人只能看到$5$个动物而且每种动物只有$0/1$两种状态，这提示我们使用状压来做

不妨先考虑环的问题，显然可以每$5$个划分状态

设$f[i][s]$表示从到$i$且$[i,i+5)$这几个动物的状态为$s$时最多能使多少小朋友开心

$f[i][s]=\max(f[i-1][(s\&15)<<1],f[i-1][(s\&15)<<1|1])+sum[i][s]$

$sum[i][s]$表示状态是$s$，视野为$[i,i+5)$的小朋友高兴的人数

• 对环的处理

环上第$n$个动物时的状态$s$的后四位必须与第$1$个动物的前四位的状态相同

则只需强制开始状态和结束状态一样才能更新，可以通过外层在加一个循环来表示初始状态来实现，具体见代码

复杂度为$O(32^2\times n)$，期望得分：$100$

代码见P3622 [APIO2007]动物园

P2150 [NOI2015]寿司晚宴

P2150 [NOI2015]寿司晚宴

给定$n-1$中不同的寿司，第$i$种寿司的美味度为$i+1$，小$G$和小$W$从中挑选一些来品尝，要求他们选得寿司中美味度必须都互质，问有多少种方案（对$p$取模）

$2\le n \le500,0<p\le10^9$

• $30pts$

$n\le 30$一共有$10$个质数，我们可以状压一下两人已经选的集合

显然对于一个寿司，如果它的质因子都不在在小$G$的集合里，那么它可以放入小$W$的集合里面

$f[i][s1][s2]$表示到第$i$个寿司，小$G$选择的质因子集合是$s1$,小$W$选的是$s2$

$\left{\begin{matrix} f[i][s1|p_i][s2]+=f[i-1][s1][s2] & p_i&s2=0 \ f[i][s1][s2|p_i]+=f[i-1][s1][s2] & p_i&s1=0 \end{matrix}\right. $

$p_i$为第$i$个寿司的质因数集合

上述转移方程竟然可以通过滚动数组来优化（奇怪的知识增加了

复杂度$O(2^{10}\times n)$，期望得分$30$

• $40pts$

没想到有什么只能过$40pts$的，如果有只能过$40pts$的麻烦告诉蒟蒻一下

• $70pts$

同样不知道,$qwq$

• $100pts$

对于$1$个数$n$它至多有$1$个$>\sqrt{n}$的质因子

根据上面的性质，我们没必要把所有质因子都状压，只需要将质因子进行分类

一类是”小因子“$<\sqrt{n}$，一类是大“因子”$> \sqrt{n}$

用$a[i].first$表示大因子集合，用$a[i].second$表示小因子集合

所有大因子相同的数显然只能放在一个集合中，所以按照大因子的大小排序，这样就可以把所有大因子相同的数放在一起算

在计算一段相同的大因子的数时，我们可以把$f[s1][s2]$拆成$g1[s1][s2]$和$g2[s1][s2]$分别表示这段数都放在集合$1$和集合$2$里的答案，$g1,g2$仍按照$30pts$的方程进行转移即可

则$f[s1][s2]=g1[s1][s2]+g2[s1][s2]-f[s1][s2]$($f[s1][s2]$加了两遍)

最终答案$ans=\sum\limits_{s1}\sum\limits_{s2}f[s1][s2]$

注意$s1=0$和$s2=0$的情况

代码见P2150 [NOI2015]寿司晚宴

树形 DP

顾名思义就是在树上进行的$DP$ ，在设计状态是通常考虑子树如何才能最优，然后考虑怎么用子树更新根节点

常见于在树上统计子树和，在树上选一些点满足价值最大，花费最少的费用覆盖所有点,树上统计方案数问题等问题中

常见的规律：

一般来说树形$dp$在设状态转移方程时都可以用$f[i][]$表示$i$这颗子树怎么怎么样的最优解，实现时一般都是用子树更新父亲（即从下向上更新），那么首先应该考虑的是一个一个子树的更新父亲还是把所有子树都算完了在更新父亲？这就要因题而异了，一般来说有两种情况：

1. 需要把所有子树的信息都掌握之后再更新子树的就需要把所有子树都算完了在更新父亲。
2. 而像树上背包这样的问题就需要一个一个的更新，每次都用一个子树更新已经更新完的子树+父亲，最后就可以将这一部分的子树更新完了，再继续往上更新，最后根节点就是答案。

其实上面的两种情况可以总结成一种情况就是一个个子树更新父亲，一般来说第一种情况应用更多，也能解决第二情况的问题，只不过如果符合第二种情况的时候用第二种可以速度更快一点，毕竟你省了一遍循环嘛。

原文链接：https://blog.csdn.net/dcx2001/article/details/78269908

CF767C Garland

CF767C Garland

把一棵$n$个节点树切成$3$部分，使得每一部分的点权和相等。

$n \le 10^6$

设所有的节点的权值和为$sum$，$f[u]$表示以$u$为根的子树的权值和

$f[u]=a[u]+\sum\limits_{v\in son_u}f[v]$

如果$u$有一个儿子$v$使得$f[v]=\frac{sum}{3}$则，我们将$v$切开，并且将$f[u]-=f[v]$

最后统计是否有两个切点即可

代码见CF767C Garland

P3942 将军令

P3942 将军令

给定$n$个节点的树，节点上可以放小队，每个小队可以控制距离该点不超过$k$的所有点，问最少放多少小队能全部控制$n$个节点

$n\le10^5,k\le 20$

• $5pts$

直接输出$n$

• $45pts，k=1$

和P2279 [HNOI2003]消防局的设立很类似，设$f[i][0/1/2]$表示$i$这个点被儿子$0$，自己$1$,被父亲$2$控制

$f[u][0]=sum( \min (f[v][0],f[v][1]))- \min(0,\max(f[v][1]-f[v][0]) ) $

$f[u][1]=sum(\min(f[v]))$

$f[u][2]=sum(\min(f[v][0],f[v][1]))$

• $75pts，k=2$

和上面的一样，只要在第二维再加两个状态，孙子和儿子全部控制但自己没被控制$3$和孙子全被控制但是自己和儿子不全被控制$4$

• $90pts$

依旧再加状态，不在赘述

• $100pts$

• 贪心$100pts$

这种题目有个结论，一定是在该点的$k$级祖先（若没有则是根节点）

那么从下往上更新答案即可
代码见P3942 将军令

P3523 [POI2011]DYN-Dynamite

P3523 [POI2011]DYN-Dynamite

给一棵树,书上有一些关键节点，要求你选m个点，使得关键节点到这些点中距离的最小值的最大值最小，求这个值

看完题目就感觉到浓浓的二分答案的味道，显然外层有个二分答案

在树上选 $tot$ 个点，使得这 $tot$ 个点与关键节点的最小距离不超过$mid$，最小化 $tot$。

问题可以继续转化：

在树上选 $tot$ 个点，每个点可以覆盖距离不超过$mid$的点， 最少几个点能将关键点全部覆盖

这就和将军令一样，变成最小点覆盖问题了

$f1[x]$：$x$的子树中未被覆盖的最远的关键节点的距离

$f2[x]$：$x$的子树中最近选择节点的距离

则$f1,f2$转移

$f1[x]=\max(f1[u])+1$

$f2[x]=\min(f2[u])+1$

然后根据$f1,f2$的几种情况，统计答案即可，这里就不写了，自己看代码吧（懒得写了我不会

代码见P3523 [POI2011]DYN-Dynamite

P3177 [HAOI2015]树上染色

P3177 [HAOI2015]树上染色

一棵$n$个点的数，将$k$个点染成黑色的，其他$n-k$个点是白色的，使黑点两两距离和加白点两两距离和最大

$0\le n,k\le 2000$

一开始想的是$f[i][j]$表示以$i$为根的子树中有$j$个黑点的最大距离和

经过一番思考摸鱼后，这样似乎没法转移，主要问题在于没法再确定$i$是黑是白的情况下计算贡献

我们考虑一下怎么计算贡献，对于两个同色点之间的距离我们可以看成是路径的和，路径上的和就是路径上边的和，我们可以通过统计每个边被同色点的路径经过次数来统计最后答案

设$k$为当前子节点的子树上已选择的黑点数，显然一条边被经过的次数为：

$tot=k\cdot(m-k)+(size[v]-k)\cdot(n-m-size[v]+k)$

这样上面的状态就不太合适了，修改一下$f[i][j]$表示以$i$为根的子树中有$j$个黑点对答案的最大贡献

$f[u][j]=\max(f[u][j],f[u][j-k]+f[to][k]+tot\cdot e[i].w)$