[自用] DP问题例题总结

ajcxsu
ajcxsu 2018年04月06日
  • 15 次阅读

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

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前面打饭更好
于是以此标准先排序

状态:dp[i][j] 前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://acxblog.site/archives/dp_problems.html
本文采用 CC BY-NC-SA 3.0 协议进行许可