2022 icpc杭州站 C. No Bug No Game - 背包dp

题面

分析

能拿整个$p_i$的就拿整个的，不能拿了可以拿一部分的，因此可以分成0和1两种情况，0表示拿整个的，1表示还可以拿部分的，两种情况放在一起做一遍01背包，找到最大价值。

代码

#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 3010;int dp[N][N][2];
int w[N][20];
int p[N];signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;int sum = 0;for(int i = 1; i <= n; i ++) {cin >> p[i];sum += p[i];for(int j = 1; j <= p[i]; j ++) cin >> w[i][j];}if(sum <= m) {int ans = 0;for(int i = 1; i <= n; i ++) ans += w[i][p[i]];cout << ans << "\n";return 0;}memset(dp, -0x3f, sizeof dp);dp[0][0][0] = 0;for(int i = 1; i <= n; i ++) {for(int j = 0; j <= m; j ++) {dp[i][j][0] = dp[i - 1][j][0];dp[i][j][1] = dp[i - 1][j][1];if(j >= p[i]) {dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - p[i]][0] + w[i][p[i]]);dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - p[i]][1] + w[i][p[i]]);}for(int k = 1; k < p[i]; k ++) {if(j >= k) dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - k][0] + w[i][k]);}}}cout << max(dp[n][m][0], dp[n][m][1]) << "\n";
}