[luoguP2760] 科技庄园（背包DP）

传送门

每次拿完还得回去。。。

数据中有两个需要注意的地方：

1. 存在桃树上有桃子但是摘 0 次的情况
2. 题目中要求体力不能为0，因此就算到达了重点体力也不能为0，所以实际上允许使用的体力为 a 1

把每个桃树想象成物品，体力和时间的最小值想象成空间

由于摘完一次就要回到起点，所以每颗桃树的体力为 2 * (x + y), x y 分别为此桃树对应的横纵坐标

#include <cstdio> #include <iostream> #define N 1001 #define M 1000001 #define min(x, y) ((x) < (y) ? (x) : (y)) #define max(x, y) ((x) > (y) ? (x) : (y)) int n, m, t, d, c, cnt; int a[N][N], b[N][N], num[M], val[M], cost[M], f[M]; inline int read() int main() } cnt = 0; for(i = 1; i <= n; i++) for(j = 1; j <= m; j++) } for(i = 1; i <= cnt; i++) for(j = c; j >= 1; j) for(k = 1; k <= num[i]; k++) if(j >= cost[i] * k) f[j] = max(f[j], f[j k * cost[i]] + k * val[i]); printf("%d\n", f[c]); return 0; }

　　

上一篇：[luoguP1156] 垃圾陷阱（DP）

下一篇：[luoguP1010] 幂次方 ^(*￣(oo)￣)^

---

DP