题目传送门 题意很明显,就不细说了 我们这里可以把剩下的忍耐度看作背包容量,然后价值就是杀了怪所得的经验 用第二维表示杀了q只怪,这样就能用dp[j][q]
表示已消耗j点忍耐度,杀了q只怪时的经验值 状态转移方程 a[i]表示杀死i怪物所获得的经验 b[i]表示杀死i怪物所消耗的忍耐值 对于第i个怪物: (1)杀:此时我们消耗点忍耐度,同时击杀怪物数+1,并且获得a[i]点经验 (2)不杀:此时我们忍耐度不变,击杀怪物数不变,由于空间已经优化到二维,所以有dp[j][q]=dp[j][q] 综合即为上述状态转移方程 代码如下:
1 |
|