DP练习
_YHY_
·
·
个人记录
P3628 [APIO2010]特别行动队
设f_i表示已经分好了前i个士兵所获得的最大战斗力，可以写出dp式子
f_i=\max_{j=0}^{i-1}f_j+a(s_i-s_j)^2+b(s_i-s_j)+c
考虑斜率优化
f_i=f_j+a(s_i-s_j)^2+b(s_i-s_j)+c
f_i=f_j+a\times s_i^2-a\times 2s_is_j+a\times s_j^2+b\times s_i-b\times s_j+c
考虑什么情况下一个决策点会比另一个更优
f_j-a\times 2s_is_j+a\times s_j^2-b\times s_j\le f_k-a\times 2s_is_k+a\times s_k^2-b\times s_k
s_i(a\times 2s_k-a\times 2s_j)\le f_k-f_j+s_k^2-s_j^2-s_k+s_j
s_i\le \frac{f_k-f_j+s_k^2-s_j^2-s_k+s_j}{a\times 2s_k-a\times 2s_j}
因为s_i是单调递增的，所以不等式右侧也要是单调递增的，用单调队列维护即可
P5504 [JSOI2011] 柠檬
首先发现一个性质，每个小段的左右端点大小一定相同，且这一段的s_0一定是左右端点的大小
写出式子
f_i=\max_{j=1}^{i}f_{j-1}+s_i(c_i-c_j+1)
其中c_i表示该位置的柠檬是相同大小的第几个
斜率优化可得
s_ic_i\le \frac{f_{k-1}+s_kc_k^2-2s_kc_k-f_{j-1}-s_jc_j^2+2s_jc_j}{2c_k-2c_j}
P3648 [APIO2014]序列分割
发现答案和分割的顺序无关，只和分割的位置有关
设f_{i,j}表示前i个元素分成j个块的最大分数，滚动掉第二维
f_i=\max_{j=0}^{i-1}f_j+s_j(s_i-s_j)
斜率优化可得
s_i\le \frac{f_k-s_k^2-f_j+s_j^2}{s_j-s_k}
P2657 [SCOI2009] windy 数
将询问区间[a,b]转化为[1,a-1]和[1,b]
数位dp，使用记忆化搜索写法
设dp[i][j][0/1][0/1]表示从高到低第i位，前一位数字是j，之前的数是否与最大值相同，有无前导零
P2602 [ZJOI2010]数字计数
dp数组含义同上，对于每一个数码dp一次
P4124 [CQOI2016]手机号码
设dp[i][j][k][0/1][0/1][0/1][0/1]表示从高到低第i位，前一位数字是j，前前一位数字是k，之前是否出现过4，是否出现过8，之前的数是否与最大值相同，是否出现过连续三个相同
P1654 OSU!
若当前已经有了x个连续的1，考虑再增加一个1对于答案贡献的期望
(x+1)^3=x^3+3x^2+3x+1
(x+1)^2=x^2+2x+1
分别维护x^3，x^2，x
x1_i=(x1_{i-1}+1)\times p_i
x2_i=(x2_{i-1}+2\times x1_{i-1}+1)\times p_i
ans_i=ans_{i-1}+(3\times x2_{i-1}+3\times x1_{i-1}+1)\times p_i
CF235B Let's Play Osu!
双倍经验
P4550 收集邮票
设f_i表示已经获得了i种邮票，还需要几次才能获得所有邮票，显然f_n=0
f_i=1+\frac{i}{n}\times f_i+\frac{n-i}{n}\times f_{i+1}
f_i=f_{i+1}+\frac{n}{n-i}
设g_i表示已经获得了i种邮票，还需要多少钱才能获得所有邮票，显然g_n=0
g_i=\frac{i}{n}\times (g_i+f_i+1)+\frac{n-i}{n}\times (g_{i+1}+f_{i+1}+1)
g_i=g_{i+1}+f_{i+1}+\frac{i}{n-i}\times f_i+\frac{n}{n-i}
P3802 小魔女帕琪
这道题不是dp题，但有助于对概率期望加深理解
考虑前七个各不相同的概率
\frac{a_1}{N}\times \frac{a_2}{N-1}\times \frac{a_3}{N-2}\times \frac{a_4}{N-3}\times \frac{a_5}{N-4}\times \frac{a_6}{N-5}\times \frac{a_7}{N-6}
一共有7!种排列，所以前七个的贡献是
7!\times \frac{a_1}{N}\times \frac{a_2}{N-1}\times \frac{a_3}{N-2}\times \frac{a_4}{N-3}\times \frac{a_5}{N-4}\times \frac{a_6}{N-5}\times \frac{a_7}{N-6}
现在考虑第2-8个各不相同的概率
假设第一个为a_1
\frac{a_1}{N}\times \frac{a_2}{N-1}\times \frac{a_3}{N-2}\times \frac{a_4}{N-3}\times \frac{a_5}{N-4}\times \frac{a_6}{N-5}\times \frac{a_7}{N-6}\times \frac{a_1-1}{N-7}
同样第2-8个有7!种排列
7!\times \frac{a_1}{N}\times \frac{a_2}{N-1}\times \frac{a_3}{N-2}\times \frac{a_4}{N-3}\times \frac{a_5}{N-4}\times \frac{a_6}{N-5}\times \frac{a_7}{N-6}\times \frac{a_1-1}{N-7}
第一个为a_2
7!\times \frac{a_2}{N}\times \frac{a_3}{N-1}\times \frac{a_4}{N-2}\times \frac{a_5}{N-3}\times \frac{a_6}{N-4}\times \frac{a_7}{N-5}\times \frac{a_1}{N-6}\times \frac{a_2-1}{N-7}
以此类推，发现每个式子的最后一项加起来是1
所以第2-8个各不相同的概率与1-7个相同，所以最终答案为
7!\times \frac{a_1}{N}\times \frac{a_2}{N-1}\times \frac{a_3}{N-2}\times \frac{a_4}{N-3}\times \frac{a_5}{N-4}\times \frac{a_6}{N-5}\times a_7
P3232 [HNOI2013]游走
考虑贪心，将每条边按照期望经过次数由大到小排序，然后由大到小编号
由于边数太大，将边的期望经过次数g_i转化为点的期望经过次数f_i
g_i=\frac{f_v}{\deg_v}+\frac{f_u}{\deg_u}(u\neq n,v\neq n)
现在的问题就是计算f数组
f_u=\begin{cases}\sum_{(u,v)\in Edge}\frac{f_v}{\deg_v}+1,u=1\\\sum_{(u,v)\in Edge}\frac{f_v}{\deg_v},1<u<n \end{cases}
高斯消元计算即可
P3750 [六省联考2017]分手是祝愿
先考虑最优策略是什么
发现对于当前编号最大的开着的灯，直接关掉它一定是最优的，所以只要从大到小扫一遍，遇到亮的就关掉，最后的操作方案就是最优的，我们只要求出做完这些操作的期望操作次数就行
设f_i表示从还剩i个操作到还剩i-1个操作的期望次数
f_i=\frac{i}{n}\times 1+\frac{n-i}{n}\times (f_i+f_{i+1}+1)
f_i=\frac{n+(n-i)\times f_{i+1}}{i}
如果最开始的最优操作次数小于k，那么答案就是这个次数，否则答案就是f_{cnt}+f_{cnt-1}+...+f_{k+1}+k，最后再乘上n!即可
P4284 [SHOI2014]概率充电器
因为每个结点的的贡献为1所以这道题的期望就是概率
考虑一个结点可以如何充电
-
自己给自己充
-
自己的儿子给自己充
-
自己的父亲给自己充
因为既有儿子的贡献又有父亲的贡献，所以要用到树形dp的up and down
设f_i为i号节点充电的概率，初始为f_i=q_i
如何合并两个结点的值
设一个事件发生的概率为P(A)，另一个事件发生的概率为P(B)，则这两个事件至少有一个发生的概率为
P(A)+P(B)-P(A)\times P(B)
所以转移方程为
f_u=f_u+f_v\times p(u,v)-f_u\times f_v\times p(u,v)
设P(B)=f_v\times p(u,v)
f_u=P(A)+P(B)-P(A)\times P(B)
$$P(A)=\frac{f_u-P(B)}{1-P(B)}$$
$$f_v=f_v+P(A)\times p(u,v)-f_v\times P(A)\times p(u,v)$$
## [P3272 [SCOI2011]地板](https://www.luogu.com.cn/problem/P3272)
插头dp模版
先考虑状态表示：$0$表示没有被穿过，$1$表示被穿过且穿过前没有拐弯，$2$表示被穿过且穿过前拐过弯
考虑如何转移
1. $11\Rightarrow 00
-
01\Rightarrow 02/10
-
10\Rightarrow 20/01
-
02\Rightarrow 00/20
-
20\Rightarrow 00/02
-
00\Rightarrow 22/10/01
P3622 [APIO2007] 动物园
考虑状压，每个围栏里的动物可以选择不撤走或撤走，用0/1表示
但围栏总数有10^4个，不能用状压表示，但我们发现每个小朋友只能看到5个围栏，于是可以每5个围栏状压一下
设f[i][s]表示\{i,i+1,i+2,i+3,i+4\}这几个围栏中动物被移走的状态为s的最大开心的小朋友数量，于是可以写出dp式子
f[i][s]=max(f[j-1][(s\And 15)<<1],f[j-1][(s\And 15)<<1|1])+g[j][s]
其中g[i][s]是预处理出来的数组，表示观看范围为\{i,i+1,i+2,i+3,i+4\}这些围栏的小朋友中，当这些围栏的状态为s时有多少时开心的
P3204 [HNOI2010] 公交线路
可以将问题转化为有一个长度为N的序列，每个位置要填充一个[1,K]的数，对于任意的1\leq i\leq K，序列的第i个位置已经被填充，填充的数为i，同时[N-K+1,N]区间内填充的数必须包含[1,K]的所有数，序列中任意一个长度为P的一段，都必须填充有[1,K]的所有数
发现K和P都比较小，所以可以考虑状压dp，设f[i][s]表示\{i,i+1,...,i+P-1\}这些位置填充的状态为s的方案数
因为我们保证每个时刻s表示的区间填充的数都各不相同，所以并不用记录填了那些数，只需要关心填了那些位置，同时，因为要保证每个位置都被填充，所以s的最高位始终都要是1
也可以理解为每次转移都是让最靠后的那辆车走到他的下一个停靠点
但这个dp是无法通过此题的，我们发现每个状态能转移到那些状态是固定的，所以考虑矩阵优化
构造矩阵f[i][j]，若编号i的状态可以转移到编号为j的状态，f[i][j]就为1，最后进行N-K次矩阵快速幂，再乘上初始矩阵即可
P3226 [HNOI2012]集合选数
构造一个矩阵，第一行第一列的数为1，每个数横行的下一个数是这个数的两倍，每个数竖列的下一个数是这个数的三倍，问题转化为在这个矩阵里选一些数，相邻的数不能选
发现矩阵的长和宽都是\log级别的，所以考虑状压dp，对n以内所有不是2和3倍数的数构造矩阵，最后乘法原理相乘即可
P2470 [SCOI2007]压缩
可以发现，在一个字符串中插入一个M，表示将这个字符串分成了独立的两部分，每个部分相当于一个可以独立计算的新字符串，于是我们可以通过M将大区间分为子区间，这就是区间dp的本质
设f_{i,j,0/1}表示区间[i,j]的答案，0表示无M，1表示有M
先考虑f_{i,j,0},若前半段和后半段相等，那么
f_{i,j}=\min(f_{i,j,0},f_{i,mid,0}+1)
然后枚举中间点转移
f_{i,j,0}=\min(f_{i,j,0},f_{i,k,0}+j-k)
然后考虑f_{i,j,1}，枚举在那个点插入M
f_{i,j,1}=\min(f_{i,j,1},\min(f_{i,k,0},f_{i,k,1})+\min(f_{k+1,j,0},f_{k+1,j,1})+1)
最后答案为\min(f_{1,n,0},f_{1,n,1})
P4158 [SCOI2009]粉刷匠
区间dp，设f_{i,j}表示前i个木板，粉刷j次最多能正确粉刷的格子数，g_{i,j,k}表示第i个木板，粉刷j次，刷了前k个格子，最多能正确粉刷的格子数
f_{i,j}=\max(f_{i,j},f_{i-1,j-k}+g_{i,k,m})
g_{i,j,k}=\max(g_{i,j,k},g_{i,j-1,l}+\max(sum_{i,k}-sum_{i,l},k-l-sum_{i,k}+sum_{i,l}))
用sum_{i,j}表示第i块木板前j个格子应该被粉刷多少个蓝色格子，相当于前缀和
P1450 [HAOI2008]硬币购物
多重背包模型，但直接多重背包做肯定会超时，多重背包和完全背包的不同就在于多重背包限制了每种物品选择的次数，只有4种物品，完全背包是可做的，所以先考虑没有次数限制的情况
f[j]=f[j]+f[j-c_i]
然后要减去不合法的，考虑第i种物品取了超过d_i的情况,即f[s-c_i\times (d_i+1)]
可以理解为先取出d_i+1个i物品，之后随便取，这样就保证了i物品一定超过d_i
用f[s]先减去每一种物品取多的情况，再加上每两种物品取多的情况，再减去每三种物品取多的情况，再加上每四种物品取多的情况就是答案
P5664 [CSP-S2019] Emiya 家今天的饭
合法的方案数不好算，所以考虑用总方案数减去不合法的方案数
发现如果存在列不合法，一定只有一列不合法，因为不可能有两列都超过总个数的一半
所以可以枚举不合法的列，设f_{i,j,k}表示前i行在当前列选了j个数，在其他列选了k个数的方案数，设c为当前列的编号，s_i为第i行的和
f_{i,j,k}=f_{i-1,j,k}+a_{i,c}\times f_{i-1,j-1,k}+(s_i-a_{i,c})\times f_{i-1,j,k-1}
即考虑第i行有没有选，以及是否选在了第c列
不合法的方案总数为
\sum_{j<k}f_{n,j,k}
但是这样枚举是O(mn^3)的，无法通过此题，发现其实并不需要知道j和k的具体数值，只需要知道相对大小关系即可
重新设计状态，设f_{i,j}表示前i行，当前列比其他列多选了j个的方案数
f_{i,j}=f_{i-1,j}+a_{i,c}\times f_{i-1,j-1}+(s_i-a_{i,c})\times f_{i-1,j+1}
这样复杂度变为了O(mn^2)
然后计算总方案数，设g_{i,j}表示前i行共选了j个数的方案数
g_{i,j}=g_{i-1,j}+s_i\times g_{i-1,j-1}
复杂度O(n^2)，总复杂度O(mn^2)
P3349 [ZJOI2016]小星星
题意简化：给定一棵树和一张图，给树上的点编号，保证编号是1到n的排列，并且对于树上的每一条边(u,v)都能再图上找到对应的边求编号的方案数
先考虑朴素的dp，设f_{i,j,S}表示i的编号为j，且i的子树的编号集合为S的方案数，转移方程为
f_{i,j,k}=\prod_{p\in son}\sum_{(q,j)\in Edge}\sum_{l\subseteq k}f_{p,q,l}
这样转移的复杂度是O(3^nn^3)，显然无法通过
发现枚举子集的复杂度是十分巨大的，而不去枚举子集就无法满足1到n的排列的限制，考虑先不考虑这个限制，在减去不合法的方案
设f_{i,j}表示i的编号为j的方案数，转移方程为
f_{i,j}=\prod_{p\in son}\sum_{(q,j)\in Edge}f_{p,q}
考虑如何计算不合法的方案数，根据鸽笼原理，n个点的编号在1到n-1的范围里，至少会有两个点编号相同
所以可以用至少0个点编号相同的方案数-至少2个点编号相同的方案数+至少3个点编号相同的方案数-至少4个点编号相同的方案数······
枚举S的所有子集，对于每个子集dp一次，复杂度O(2^nn^3)
P3813 [FJOI2017]矩阵填数
先把每个格子分开考虑，一个格子能填的数的值域为[1,\min(v_i,m)]，其中v_i为该格子所在的子矩阵
如果两个最大值不同的格子取到各自的最大值，那么它们满足的子矩阵一定是不同的，所以不同值域的格子互不影响
那么可以分值域考虑
设S_k表示最大值为k的格子的集合，则总方案数为k^{|S_k|}
现在要减去不合法的方案数，即某些子矩阵没有满足要求的方案数
考虑容斥
设$T_{k,i}$表示集合$S_k$中属于$i$号子矩阵的格子的集合，不合法的方案数为$(k-1)^{|T_{k,i}|}k^{|S_k|-|T_{k,i}|}
先减去1号子矩阵不满足要求的方案数、2号子矩阵不满足要求的方案数······，然后加上1,2同时不满足的方案数，2,3同时不满足的方案数，1,3同时不满足的方案数······，减去1,2,3同时不满足的方案数······
枚举v值相同的子矩阵集合的子集计算|T|，然后根据集合大小计算容斥系数即可
P3158 [CQOI2011]放棋子
设f[k][i][j]表示前k种颜色的棋子占领了任意i行j列的方案数，转移方程为
f[k][i][j]=\sum_{l=1}^{i-1}\sum_{r=1}^{j-1}f[k-1][l][r]\times g[a[k]][i-l][j-r]\times C_{n-i}^{i-l}\times C_{m-r}^{j-r}((i-l)\times (j-r)\ge a[k])
$$g[k][i][j]= C_{i \times j}^{k} - \sum_{l = 1}^i \sum_{r = 1}^j g[k][l][r] \times C_i^l \times C_j^r(l<i||r<j,i\times j\ge k)$$
因为不需要占领所有的行和列，所以最后的答案为$\sum_{i=1}^n\sum_{j=1}^m f[c][i][j]
P2467 [SDOI2010]地精部落
题意简化：求1到n的排列中波动序列的个数
波动序列有两个重要性质
-
对于一个波动序列，若i和i+1不相邻，交换它们后序列仍然是波动序列
-
对于一个波动序列，将所有元素变为n-a_i+1后仍然是波动序列
设f_{i,j}表示长度为i的波动序列，第一个元素为j且j为波峰的方案数，考虑j和j-1的位置关系
-
若j和j-1不相邻，由性质1得，开头为j和开头j-1的波动序列是一一对应的，所以f_{i,j}+=f_{i,j-1}
-
若j和j-1相邻，j为波峰，那么j-1就为波谷，由性质2得，波谷为j-1的长度为i-1的波动序列和波峰为i-j+1的长度为i-1的波动序列是一一对应的，所以f_{i,j}+=f_{i-1,i-j+1}
总的DP转移方程为
f_{i,j}=f_{i-1,n-j+1}+f_{i,j-1}
P4104 [HEOI2014]平衡
根据杠杆平衡条件，F_1l_1=F_2l_2，即左侧橡皮到支点的距离和等于右侧橡皮到支点的距离和
将刻度线从左到右标号1到2n+1，即满足i\times (n+1)-sum_1=sum_2-(k-i)\times (n+1)
移项得sum1+sum2=k\times (n+1)
现在问题转化为将k\times (n+1)拆分为k个1到2n+1内的不相等的数
设f_{i,j}表示用i个数来拆分j的方案数，考虑如何通过一个已有数列得到一个新的数列，分两种情况讨论
-
若最小值不为1，虽然不确定原数列最小值是不是1，但是给原数列的每个数加上1一定是满足要求的，且新数列和原数列是一一对应的，所以f_{i,j}+=f_{i,j-i}
-
若最小值为1，可以先给原数列每个数都加上一，再添加一个1，这样的新数列和原数列也是一一对应的，所以f_{i,j}+=f_{i-1,j-i}
总的dp转移方程为f_{i,j}=f_{i-1,j-i}+f_{i,j-i}
P4253 [SCOI2015]小凸玩密室
设f[i][j]表示点亮i之后回到i的第j个祖先的最小花费
设g[i][j]表示点亮i之后回到i的第j个祖先的另一个儿子的最小花费
先更新g
-
若i为叶子g[i][j]=(dis[i][j]+dis[brother(i,j)][1])\times w[brother(i,j)]
-
若i只有左儿子g[i][j]=dis[ls[i]][1]\times w[ls[i]]+g[ls[i]][j+1]
-
若i两个儿子都有g[i][j]=\min(dis[ls[i]][1]\times w[ls[i]]+g[ls[i]][1]+g[rs[i]][j+1],dis[rs[i]][1]\times w[rs[i]]+g[rs[i]][1]+g[ls[i]][j+1])
再更新f
-
若i为叶子f[i][j]=dis[i][j]\times w[fa[i]]
-
若i只有左儿子f[i][j]=f[ls[i]][j+1]+dis[ls[i]][1]\times w[ls[i]]
-
若i两个儿子都有f[i][j]=\min(dis[ls[i]][1]\times w[ls[i]]+g[ls[i]][1]+f[rs[i]][j+1],dis[rs[i]][1]\times w[rs[i]]+g[rs[i]][1]+f[ls[i]][j+1])
最后统计答案时枚举起点，然后按照点亮的顺序统计即可
CF1557D Ezzat and Grid
先将区间离散化，考虑朴素的dp，题目中要求删掉的最少行数，可以转化为留下的最大行数，所以设f_i表示前i行最多留下几行，转移方程为
f_i=\max_{j=1}^{i-1}f_j\times g_{i,j}+1
g_{i,j}$表示第$i$行与第$j$行是否有相同的一列被涂黑，dp的复杂度为$O(n)$，但预处理$g$数组的复杂度为$O(n^3)
考虑用线段树优化dp
线段树下标为i的地方维护的是所有第i列被涂黑的行的f的最大值，转移时在当前行被涂黑的下标的区间查询最大值，转移完一行后再更新线段树中的值