[自用] DP问题例题总结

Author Avatar
空気浮遊 2018年04月06日
  • 在其它设备中阅读本文章

如果是自己写的就标个星号

LP1373 小 a 和 uim 之大逃离 [差值 dp]

Problem

https://www.luogu.org/problemnew/show/P1373

Solution

原 dp 方程:$dp[i][j][a][b][0,1]$ 走到格 i,j, 两人手上有的权值为 a,b,0 代表小 a 取,1 代表 uim 取。

优化:由于只要两人的权值相等,可以转化成权值差进行 dp。

优化后方程:$dp[i][j][x][0,1]$ 走到格 i,j,两人手上的权值差为 x,balabala

转移:不多 bb

LP2577 [ZJOI2005]午餐 [奇妙 dp] ※

Problem

https://www.luogu.org/problemnew/show/P2577

Solution

假设只有一个队伍,队伍的打饭时间达到 T
有人 i,j,打饭时间和吃饭时间分别为 ti,ei,tj,ej
当 max(T+ti+ei, T+ti+tj+ej) < max(T+tj+ej, T+ti+tj+ei)时,i 排在 j 前面打饭更好
于是以此标准先排序

状态:dpi 前 i 个人打饭,A 队的打饭时间为 j B 队打饭时间记个 tot 可以直接求出
转移不多 bb

LP1070 道路游戏

Problem

https://www.luogu.org/problemnew/show/P1070

Solution

状态:f[i] 第 i 秒的最大金钱
枚举位置 j 和步数 k
f[i]=f[i-k]+sum-w[beg]
因为走 k 步要耗 k 时间
sum是走这 k 步所得到的金钱
w[beg]为买到机器人所耗的金钱,beg是起点

f[0]=0
这样子复杂度理论上来说是 $O(0.5n^3)$,炸了
然而并没有
只能说数据稍微水一点

正解是单调队列?
但我已经不想做了 emm