DP没入门就入土

写在前面

记录最近刷的DP题以及打死都不可能想到状态设计DP系列汇总

洛谷 P6082 [JSOI2015]salesman

树形$\texttt{DP}$ + 优先队列

比较容易看出来这是一道树形$\texttt{DP}$题

要注意的是最大停留次数为输入次数-1，因为还要从子树返回到这一个节点

然后下面考虑怎么$\texttt{DP}$

我们用$f[i]$表示以从$i$出发，访问以$i$为根的子树，并且最后能回到$i$的最大收益

显然我们要选较大且非负的数，因为去大点权的节点肯定比去小点权的点权更优，去非负点权的节点肯定比去负点权的节点更优，而且因为一个节点可以去多次且只记一次点权，所以肯定能够用完次数，因此我们每次在小于等于停留次数的前提下取完正儿子即可，这样就可以保证最大，所以$f[i]$就等于$i$所有正儿子的点权之和（前提是小于等于最大停留次数），最后的答案就是$f[1]$

下面来考虑解是否唯一的问题，解不唯一有两种情况：

$i$的子树中有权值为$0$的点。因为选不选权值都不变，所以可选可不选，因此解就不唯一了
如果$i$在遍历过程中当父亲节点剩余的停留次数为$1$时，可选的最大值有两个及两个以上儿子节点，则解不唯一

所以在过程中判断一下就好了

代码见洛谷 P6082 [JSOI2015]salesman

洛谷 P2831 愤怒的小鸟

未优化

状压$\text{DP}$

$n\leq 18$，不是暴搜就是状压，因为我$jio$得状压会比较好理解，所以就写一篇状压的题解叭

首先我们要预处理出经过任意两点的抛物线可以击中的小猪有哪些，可以用$line[i][j]$来表示经过$i,j$的抛物线经过的小猪的集合，集合用二进制数来表示

这里有一个小问题就是如何求抛物线$y=ax^2+bx$中的$a,b$

假设目前的抛物线经过$(x_1,y_1)$和$(x_2,y_2)$两点，已知$x>0$，那么有

\[y_1=ax_1^2+bx_1
\]

\[y_2=ax_2^2+bx_2
\]

则

\[ax_1+b=\frac{y_1}{x_1}
\]

\[ax_2+b=\frac{y_2}{x_2}
\]

两式做差得

\[a(x_1-x_2)=\frac{y_1}{x_1} - \frac{y_2}{x_2}
\]

所以

$a=\frac{\frac{y_1}{x_1} - \frac{y_2}{x_2}}{(x_1-x_2)}$

$b=\frac{y_1}{x_1}-a*x_1$

处理完之后就要想一想如何$\text{DP}$

我们设$dp[s]$表示消灭集合$s$内所有小猪所用的最少的小鸟数

显然$dp[0]=0$，因为没有猪当然用不到鸟

假设当前的状态为$s$，抛物线为经过$i,j$点的抛物线，这条抛物线打掉的小猪的状态为$line[i][j]$，那么有

\[dp[s|line[i][j]] = \min(dp[s|line[i][j]],dp[s] + 1)
\]

其中$s|line[i][j]$表示当前状态$s$在增加了经过$i,j$点的这条抛物线之后能打到的小猪的集合，显然要从$dp[s|line[i][j]]$和$dp[s]+1$中取最小

时间复杂度$O(Tn^22^n)$O(能过才怪)，在洛谷上吸氧($O2$)可以过

优化

随意选择$s$内的一只小猪$j$，那么$j$最后一定会被一只小鸟消灭，所以我们固定住这只小猪$j$，只枚举$k$转移

更详细见AThousandSuns的题解

时间复杂度$O(Tn2^n)$，稳了

代码见洛谷 P2831 愤怒的小鸟

洛谷 P4910 帕秋莉的手环

题意

多组数据，给出一个环，要求不能有连续的$1$，求出满足条件的方案数

$1\le T \le 10, 1\le n \le 10^{18}$

思路

20pts

暴力枚举（不会写

60pts

假设金珠子为$0$，木珠子为$1$，则不能有连续的木珠子

线性递推$DP$，设$f[i][0/1]$表示当前填到第$i$位，第$i$位为金珠子/木珠子的方案数，那么有：

\[f[i][0] = f[i - 1][0] + f[i - 1][1]
\]

\[f[i][1] = f[i-1][0]
\]

但是要分成两种情况讨论

第一个位置是$0$，则$f[1][0]=1,f[1][1]=0$，那么最后一个位置可以是$0$也可以是$1$

所以此时对答案的贡献为$f[n][0]+f[n][1]$
第一个位置是$1$，则$f[1][1]=1,f[1][0]=0$，那么最后一个位置只能是$0$

所以此时对答案的贡献为$f[n][0]$

时间复杂度$O(Tn)$，期望得分$60$分

不知道为什么，也许是我写假了，只有48分

100pts

考虑用矩阵优化，目前的状态为$[f_{i,0},f_{i,1}]$，目标状态为$[f_{i+1,0},f_{i+1，1}]$，比较容易推出转移矩阵为

\[[f_{i,0},f_{i,1}] * \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right] = [f_{i+1,0},f_{i+1，1}]
\]

按照$60$分做法写矩阵快速幂就好了

代码见洛谷 P4910 帕秋莉的手环

51Nod 1327 棋盘游戏

以行为状态转移无法记录各列的状态，所以以列为状态转移

设$f[i][j][k]$为处理到第$i$列，前面有$j$列没有填棋子，有$k$行已经填到了右区间的方案数

记$l[i],r[i],mid[i]$分别为左区间右端点为$i$的行数、右区间左端点为$i$的行数、第$i$列没有被左右区间覆盖的行数

每次到达左区间右端点的限制$l_{i}$时，再考虑如何满足这些左区间，则有如下三种转移：

放在左区间内，就要满足将$l_{i+1}$行安排到前面没放棋子的$j$列中，因为顺序没有要求，所以直接乘上排列数，转移为

\[f[i+1][j+1-l_{i+1}][k+r_{i+1}]+=f[i][j][k]\times A_{j+1}^{l_{i+1}}
\]
放在右区间内，要乘上左右两侧的方案数

\[f[i+1][j-l_{i+1}][k+r_{i+1}-1]+=f[i][j][k]\times A_{j}^{l_{i+1}}\times (k+r_{i+1})
\]
放在未被覆盖的中间位置，要乘上左侧和中间的方案数

\[f[i+1][j-l_{i+1}][k+r_{i+1}]+=f[i][j][k]\times mid_{i+1}\times A_{j}^{l_{i+1}}
\]

初始状态为$f[0][0][0]=1$，最后的答案为$\sum_{i=1}^{m}f[m][i][0]$

代码见51Nod 1327 棋盘游戏

51Nod 1683 最短路

题意

给定一个未知的$0/1$矩阵，对每个$i$求$(1,1)\sim(n,m)$最短路为$i$的概率，在矩阵中不能向左走，路径长度为路径上权值为$1$的格子个数。

$n\leq6,m\leq100。$

思路

打死都不可能想到状态设计DP系列

参考了这篇博客的思路【51nod1683】最短路

概率乘了$2^{n\times m}$之后其实就是方案数，所以问题转化为了求满足题目条件的方案数

发现$n$很小，最大只有$6$，考虑状压，但是不能直接维护当前格子的最短路，因为在多条并列最短路时会重复计数

考虑现在的$0/1$矩阵的特殊性：因为不能向左走，所以对于同一列中相邻两个格子之间的最短路最多相差$1$。因此考虑维护一整列最短路的差分数组。

记$zt$为一个三进制状态，表示该行从第二行开始，每个格子与上面的格子的差

设$f[i][j][zt]$表示第$i$列，第一行的最短路为$j$，第$2$行~第$n$行的最短路的三进制为$zt$的方案数

转移时需要枚举下一列的$0/1$状态，线性更新一遍状态就可以了

时间复杂度为$O(nm2^n3^{n-1})$

代码见51Nod 1683 最短路

洛谷 P3592 [POI2015]MYJ

题意

给定$m$个区间$[a_i,b_i]$以及$c_i$，对于一个含有$n$个元素的序列$ans[]$，区间$i$对其的贡献为$\min\{ans_i\}(i\in[a_i,b_i])<=c_i\ ?\ \min\{ans_i\}(i\in[a_i,b_i])\ :\ 0$，要求构造一个序列$ans[]$，最大化区间的贡献之和。

$n\leq50,m\leq4000$

思路

离散化+区间$\texttt{DP}$

稍作分析半天就会发现：存在一组答案使得每个$ans_i$都是某个$c_i$。因为把某个答案替换成第一个大于等于它的$c_i$不会更劣，因此$c_i$的值并不影响做题，但是大小顺序是有用的所以我们将$c_i$离散化。

因为一个区间的代价之和只与最小值有关，而且数据范围的$n$也不大，所以考虑区间$\texttt{DP}$：

设$f[l][r][k]$表示区间$[l,r]$内$ans[]$的最小值等于$k$的最大收益，$g[p][j]$为当前区间穿过$p$，且$c\geq j$的区间数量

枚举最小的位置$p$，那么包含$p$的区间的答案全都是$k$，之后转移

\[f[l][r][k]=\max(\max(f[l][p - 1][k] + f[p + 1][r][k]+g[p][k]*k,p\in[l,r]),f[l][r][k+1])
\]

$\texttt{DP}$时顺便记录记录决策点，然后$dfs$输出

时间复杂度$O(n^3m)$

代码见洛谷 P3592 [POI2015]MYJ

洛谷 P4042 [AHOI2014/JSOI2014]骑士游戏

题意

有$n$个怪物，可以消耗$k$的代价消灭一个怪物或者消耗$s$的代价将它变成另外一个或多个新的怪物，求消灭怪物$的最小代价

思路

$DP$+最短路

看起来像是个$\texttt{DP}$，认真思考一会儿也不难想到可以设计如下状态

设$f[i]$为消灭$i$所需的最小代价，那么有

\[f[i]=\min(f[i], s[i]+\sum\limits_{to_i} f[to_i])
\]

其中$to$表示$i$点的后继

因为$f$的转移之间相互干涉，所以用最短路处理

先建双向边，方便之后转移，然后用$\texttt{SPFA}$（它死了求"多源"最短路就好了

因为不知道一开始应该打哪个怪物，所以干脆全都入队、全部更新就好了

$ps:$两年$\text{OI}$一场空，不开$long\ long$见祖宗

代码见洛谷 P4042 [AHOI2014/JSOI2014]骑士游戏

巴特西