马上要联赛了, 我又要来抱一抱 DP 的佛脚 \(QWQ\)
最近膜你赛的题目的常规 \(dp\)都不是很难推, 但是优化这一方面确实不是很好, 所以我来这里复 (学) 习一下一些常见 DP 优化和其他类型的 DP(dalao 勿 D)qwq (未完待续)
1,P2059 [JLOI2013]卡牌游戏
2,P1850 换教室(期望 DP)
1,P2059 [JLOI2013]卡牌游戏 https://www.luogu.org/problem/P2059
这道题也是一道比较基础的 (算是) 概率 dp 吧.
我们首先可以来分析一下这道题目的状态, 我们要明白这道题的操作流程, 如果你不是很懂的话请自行那一副牌来模拟一下.
我们现在来看一下这个 \(dp\)的状态转移的方程.
\(f[i][j]\)表示还剩 \(i\)个人的时候庄家向后数 \(j\)位的时候的人获胜的概率.
所以, 我们现在来考虑一下我们 \(f[i][]\)的状态一定是从 \(f[i-1][]\)转移来, 所以我们现在就来讨论一下 \(j\)的情况.
这个时候我们可以来枚举一下当 \(j\)为庄家是所抽的牌为 \(k\)时的情况. 这时我们可以假设此时淘汰的人为 \(w\), 如果 \(w==j\)那么这个情况就不用考虑了, (自己的没了, 还玩个锤子啊)
如果,\(w<j\)的时候, 这时候 \(j\)的位置就变成了 \(j-c\)
如果,\(w>j\)的时候,\(j\)的位置就变成了 \(i-w+j\)
所以, 我们的状态转移方程就可以写出来了.
- \[f[i][j]=f[i][j]+f[i-1][i-w+j]/m (w>j) \]
- \[f[i][j]=f[i][j]+f[i-1][j-w]/m (w<j) \]
- code
回到顶部
2,P1850 换教室 (期望 DP)
https://www.luogu.org/problem/P1850
这道题是一道期望 DP 的题, 但是应该难度还不算太大. 其实就是将计算期望的方法融入到 DP 式子中.
首先, 我们可以来分析一下这道题, 我们现在已知的是每一天的原来 \(c_i\)和现在的教室 \(d_i\), 以及要到这个教室的路径贡献 \(dis[i][j]\)(可以提前预处理出来), 还有就是我们每一次换教室成功的概率 \(k_i\), 我们就可以枚举每一次的换教室的选还是不选, 然后再通过概率去进行计算期望. 这个时候, 我们的基本状态就可以设计出来了.
\(f[i][j][0/1]\)表示在 \(i\)之前的时间中有 \(j\)个教室进行了交换,\(0/1\)表示这个教室选择换还是不换的期望最小值.
现在我们来考虑如何进行转移.
当 \(f[i][j][0]\)时, 表示这个教室我们不选择进行交换, 我们来考虑一下上一个时间的状态
当上一个时间不选择交换时, 贡献
\[f[i-1][j][0]+dis[c[i-1]][c[i]]\]
当上一个时间选择交换时, 贡献
\[f[i-1][j][1]+k[i-1]*dis[d[i-1]][c[i]]+(1-k[i-1])*dis[c[i-1]][c[i]]\]
同理, 我们来考虑一下 \(f[i][j][1]\)选择这个教室进行交换的状态
当上一个时间不选择交换时, 贡献
\[f[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1-k[i])+dis[c[i-1]][c[i]]\]
当上一个时间选择交换时, 贡献
\[f[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+(1-k[i-1])*k[i]*dis[c[i-1]][d[i]]+k[i-1]*(1-k[i])*dis[d[i-1]][c[i]]+(1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]]\]
所以我们就可以把这道题解决掉了.
code
回到顶部
DP 练习
来源: http://www.bubuko.com/infodetail-3257908.html