[luoguP1156] 垃圾陷阱（DP）

传送门

先按照时间排序

f[i][j] 表示 前i个物品高度为j时所剩余的最大能量

显然每个物品有堆和吃两种选择

状态转移看代码

代码

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 1001 #define max(x, y) ((x) > (y) ? (x) : (y)) int d, g, ans; int f[N][N]; struct node p[N]; inline int read() inline bool cmp(node x, node y) int main() std::sort(p + 1, p + g + 1, cmp); memset(f, 1, sizeof(f)); f[0][0] = 10; for(i = 1; i <= g; i++) for(j = 0; j <= d; j++) } } for(i = 1; i <= g; i++) for(j = 0; j <= d; j++) if(f[i][j] ^ 1) ans = max(ans, f[i][j] + p[i].t); printf("%d\n", ans); return 0; }

　　

上一篇：[luoguP1086] 花生采摘（模拟）

下一篇：[luoguP2760] 科技庄园（背包DP）

---

DP