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

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

本文链接：https://pst.iorinn.moe/archives/dp_problems.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆