T1：垃圾游戏3
本题难度中等，一道稍有变化的01背包题。一般的01背包是考虑每个物品取和不取，本题是考虑每个物品带走（相当于取）还是分解（相当于不取），如果分解，也会贡献相应价值
记 dp[i][j] 表示前 \(i\) 个物品中选总重量不超过 \(j\) 的物品能得到的最大金币
转移：
- 分解：\(dp[i-1][j] + c_i\)
- 装走：\(dp[i-1][j-w_i] + v_i\)
\(dp[i][j]\) 是两者最大值
最终的答案是 \(dp[n][m]\)
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
int dp[1005][10005];
inline void chmax(int& x, int y) { if (x < y) x = y; }
int main() {
int n, m;
cin >> n >> m;
rep(i, n) {
int w, v, c;
cin >> w >> v >> c;
for (int j = 0; j <= m; ++j) {
int now = 0;
chmax(now, dp[i-1][j]+c);
if (j >= w) chmax(now, dp[i-1][j-w]+v);
dp[i][j] = now;
}
}
cout << dp[n][m] << '\n';
return 0;
}
T2：飞盘队2
本题难度较大，一道计算方案数的01背包问题。如果以总能力值作为背包大小，只能得到 \(60\) 分。需要以能力值除以 \(F\) 余数作为 \(dp\) 数组的第二维，并且建两个数组分别记最大总能力值和达成最大能力的方案数，仔细讨论状态转移，才能得到满分。
做法1：
记 dp[i][j] 表示从前 \(i\) 头牛中取总和为 \(j\) 的方案数
转移：
不取：dp[i][j] = dp[i-1][j]
取：dp[i][j] += dp[i-1][j-Ri] (j >= Ri)
初值：\(dp[0][0] = 1\)，其他 \(dp=0\)
答案：找到使得 \(dp[i][j] > 0\) 且 \(j\) 是 \(F\) 的倍数的最大的 \(j\)，答案是 \(j\) 和 \(dp[i][j]\)
但注意到 \(O(R_i)\) 为 \(1e5\)， \(O(\sum R_i)\) 就是 \(2e7\) 了，而 \(O(n\sum R_i)\) 就是 \(4e9\)，时间肯定要炸
做法2：
用 dp[i][j] 记录前 \(i\) 头牛中取若干头使总和除以 \(F\) 余 \(j\) 时能得到的最大总和
用 f[i][j] 记录得到最大和的方法数
初值：\(dp[0][0] = 0\), 其他 \(dp=-\infty\)；\(f[0][0] = 1\)，其他 \(f=0\)
转移：
不取：\(t_1 = dp[i-1][j]\)
取：\(t_2 = dp[i-1][((j-R_i)\%F + F)\% F] + R_i\)
\(dp[i][j] = \max(t_1, t_2)\)
若 \(t_1 > t_2\)：\(f[i][j] = f[i-1][j]\)
若 \(t_1 < t_2\)：\(f[i][j] = f[i-1][((j-R_i)\%F + F)\% F]\)
若 \(t_1 = t_2\)：\(f[i][j] = f[i-1][j] + f[i-1][((j-R_i)\%F + F)\% F]\)
答案：\(dp[n][0]\) 和 \(f[n][0]\)
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using ll = long long;
int a[205];
int dp[205][1005];
ll f[205][1005];
inline void chmax(int& x, int y) { if (x < y) x = y; }
int main() {
int n, F;
cin >> n >> F;
memset(dp, 0xcf, sizeof dp);
dp[0][0] = 0;
f[0][0] = 1;
rep(i, n) {
int r;
cin >> r;
for (int j = 0; j < F; ++j) {
int t1 = dp[i-1][j];
int nj = ((j-r)%F+F)%F;
int t2 = dp[i-1][nj]+r;
dp[i][j] = max(t1, t2);
if (t1 > t2) f[i][j] = f[i-1][j];
else if (t1 < t2) f[i][j] = f[i-1][nj];
else f[i][j] = f[i-1][j] + f[i-1][nj];
}
}
cout << dp[n][0] << '\n' << f[n][0] << '\n';
return 0;
}