写在前面
记录最近刷的DP题 以及 打死都不可能想到状态设计DP系列 汇总
洛谷 P6082 [JSOI2015]salesman
比较容易看出来这是一道树形\(\texttt{DP}\)题
要注意的是最大停留次数为输入次数-1
,因为还要从子树返回到这一个节点
然后下面考虑怎么\(\texttt{DP}\)
我们用\(f[i]\)表示以从\(i\)出发,访问以\(i\)为根的子树,并且最后能回到\(i\)的最大收益
显然我们要选较大且非负的数,因为去大点权的节点肯定比去小点权的点权更优,去非负点权的节点肯定比去负点权的节点更优,而且因为一个节点可以去多次且只记一次点权,所以肯定能够用完次数,因此我们每次在小于等于停留次数的前提下取完正儿子即可,这样就可以保证最大,所以\(f[i]\)就等于\(i\)所有正儿子的点权之和(前提是小于等于最大停留次数),最后的答案就是\(f[1]\)
下面来考虑解是否唯一的问题,解不唯一有两种情况:
- \(i\)的子树中有权值为\(0\)的点。因为选不选权值都不变,所以可选可不选,因此解就不唯一了
- 如果\(i\)在遍历过程中当父亲节点剩余的停留次数为\(1\)时,可选的最大值有两个及两个以上儿子节点,则解不唯一
所以在过程中判断一下就好了
代码见洛谷 P6082 [JSOI2015]salesman
洛谷 P2831 愤怒的小鸟
未优化
\(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]\),那么有
\]
其中\(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)\),稳了
洛谷 P4910 帕秋莉的手环
题意
多组数据,给出一个环,要求不能有连续的\(1\),求出满足条件的方案数
\(1\le T \le 10, 1\le n \le 10^{18}\)
思路
20pts
暴力枚举(不会写
60pts
假设金珠子为\(0\),木珠子为\(1\),则不能有连续的木珠子
线性递推\(DP\),设\(f[i][0/1]\)表示当前填到第\(i\)位,第\(i\)位为金珠子/木珠子的方案数,那么有:
\]
\]
但是要分成两种情况讨论
第一个位置是\(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}]\),比较容易推出转移矩阵为
\]
按照\(60\)分做法写矩阵快速幂就好了
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 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})\)
洛谷 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\)
思路
稍作分析半天就会发现:存在一组答案使得每个\(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\),之后转移
\]
\(\texttt{DP}\)时顺便记录记录决策点,然后\(dfs\)输出
时间复杂度\(O(n^3m)\)
洛谷 P4042 [AHOI2014/JSOI2014]骑士游戏
题意
有\(n\)个怪物,可以消耗\(k\)的代价消灭一个怪物或者消耗\(s\)的代价将它变成另外一个或多个新的怪物,求消灭怪物$的最小代价
思路
看起来像是个\(\texttt{DP}\),认真思考一会儿也不难想到可以设计如下状态
设\(f[i]\)为消灭\(i\)所需的最小代价,那么有
\]
其中\(to\)表示\(i\)点的后继
因为\(f\)的转移之间相互干涉,所以用最短路处理
先建双向边,方便之后转移,然后用\(\texttt{SPFA}\)(它死了求"多源"最短路就好了
因为不知道一开始应该打哪个怪物,所以干脆全都入队、全部更新就好了
\(ps:\)两年\(\text{OI}\)一场空,不开\(long\ long\)见祖宗