题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
#include <bits/stdc++.h> using namespace std; int main() { int N, m, v, p, q, v1, p1, v2, p2; cin >> N >> m; vector<vector<int>> mainGoods(m + 1); vector<vector<vector<int>>> accessories(m + 1); for (int i = 1; i <= m; i++) { cin >> v >> p >> q; if (q == 0) { mainGoods[i] = vector<int>{v, p}; }else { accessories[q].push_back({v, p}); } } vector<vector<int>> dp(m + 1, vector<int>(N + 1)); int res = 0; for (int i = 1; i <= m; i++) { if (mainGoods[i].empty()) continue; v = mainGoods[i][0]; p = mainGoods[i][1]; for (int w = v; w <= N; w += 10) { dp[i][w] = max(dp[i][w], (w >= v) ? dp[i - 1][w - v] + v * p : dp[i - 1][w]); if (accessories[i].size() >= 1) { v1 = accessories[i][0][0]; p1 = accessories[i][0][1]; dp[i][w] = max(dp[i][w], (w >= v + v1) ? dp[i - 1][w - v - v1] + v * p + v1 * p1 : dp[i - 1][w]); if(accessories[i].size() == 2) { v2 = accessories[i][1][0]; p2 = accessories[i][1][1]; dp[i][w] = max(dp[i][w], (w >= v + v2) ? dp[i - 1][w - v - v2] + v * p + v2 * p2 : dp[i - 1][w]); dp[i][w] = max(dp[i][w], (w >= v + v1 + v2) ? dp[i - 1][w - v - v1 - v2] + v * p + v1 * p1 + v2 * p2 : dp[i - 1][w]); } } // printf("i:%d, w:%d, dp:%d\n", i, w, dp[i][w]); res = max(res, dp[i][w]); } } printf("%d\n", res); return 0; }
上述代码存在两个问题:
(1) 错误的continue会导致状态转移不充分!
if (mainGoods[i].empty()) continue;
(2) 对于主件,它参考的是前一项主件,所以对应的dummy状态是dp[i - 1][w]:
dp[i][w] = max(dp[i][w], (w >= v) ? dp[i - 1][w - v] + v * p : dp[i - 1][w]); // 错误
dp[i][w] = (w >= v) ? max(dp[i - 1][w], dp[i - 1][w - v] + v * p) : dp[i - 1][w]; //正确
而对于附件,它参考的是主件,所以dummy状态是dp[i][w]dp[i][w] = max(dp[i][w], (w >= v + v1) ? dp[i - 1][w - v - v1] + v * p + v1 * p1 : dp[i - 1][w]); //错误 dp[i][w] = (w >= v + v1) ? max(dp[i - 1][w], dp[i][w - v - v1] + v * p + v1 * p1): dp[i][w]; //正确
正确的代码应该是:
#include <bits/stdc++.h> using namespace std; int main() { int N, m, v, p, q, v1, p1, v2, p2; cin >> N >> m; vector<vector<int>> mainGoods(m + 1, vector<int>(3, 0)); vector<vector<vector<int>>> accessories(m + 1); for (int i = 1; i <= m; i++) { cin >> v >> p >> q; if (q == 0) { mainGoods[i] = vector<int>{v, p}; }else { accessories[q].push_back({v, p}); } } vector<vector<int>> dp(m + 1, vector<int>(N + 1)); int res = 0; for (int i = 1; i <= m; i++) { v = mainGoods[i][0]; p = mainGoods[i][1]; for (int w = 0; w <= N; w += 10) { dp[i][w] = (w >= v) ? max(dp[i - 1][w], dp[i - 1][w - v] + v * p) : dp[i - 1][w]; if (accessories[i].size() >= 1) { v1 = accessories[i][0][0]; p1 = accessories[i][0][1]; dp[i][w] = (w >= v + v1) ? max(dp[i][w], dp[i - 1][w - v - v1] + v * p + v1 * p1) : dp[i][w]; if(accessories[i].size() == 2) { v2 = accessories[i][1][0]; p2 = accessories[i][1][1]; dp[i][w] = (w >= v + v2) ? max(dp[i][w], dp[i - 1][w - v - v2] + v * p + v2 * p2) : dp[i][w]; dp[i][w] = (w >= v + v1 + v2) ? max(dp[i][w], dp[i - 1][w - v - v1 - v2] + v * p + v1 * p1 + v2 * p2) : dp[i][w]; } } } } printf("%d\n", dp[m][N]); return 0; }