传送门
先按照时间排序
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; }
上一篇：[HDU2089] 不要62 (数位DP)
下一篇：[luoguP1981] 表达式求值（U•ェ•*U）
DP
