洛谷 P2722 总分 Score Inflation

完全背包问题

动态转移方程： f[i][j] = max(f[i - 1][j], f[i][j - c[i] + v[i])

对于任意一个f[i][j] 表示选到第i个物品时 可以不选第i件物品 即f[i - 1][j] 或者在原来选过第i的基础上再选一次 即f[i][j - c[i] + v[i] 然后在利用循环数组优化到 f[j] = max(f[j], f[j - c[i] + v[i])

特别注意： - i 和 j 是如何循环的 - 区分与01背包（不论是读题时 还是写题时）（特别要小心样例在此处坑你）

//P2722 总分 Score Inflation //2016.11.18 #include <cstdio> #include <iostream> #define MAXN 10000 + 2 using namespace std; int m, n, s, t; int f[MAXN]; int main(){ scanf("%d%d", &m, &n); for (int i = 1; i <= n; i++){ scanf("%d%d", &s, &t); for (int j = t; j <= m; j++) f[j] = max(f[j], f[j - t] + s); } printf("%d", f[m]); return 0; }