牛客背包问题练习 xinjun与阴阳师
题目链接：题目
大意：
有一定体力，有n种模式，每种模式又有几种操作，每个操作有对应价值和体力消耗，每种模式只能最多选一种操作，求最大价值。
思路：
选与不选，也就是背包问题，只不过比传统的背包问题多了一些可选项，并且优化成一维的dp数组。
代码：
#include <bits/stdc++.h>
using namespace std; #define int long long
#define MOD 1000000007
#define fi first
#define se second
#define pii pair<int,int>
#define vec vector void solve(){ int n, m; cin >> n >> m; vec<vec<int>> av(n), aw(n); for(int i = 0; i < n; i++){ int a; cin >> a; for(int j = 0; j < a; j++){ int v; cin >> v; av[i].push_back(v); } for(int j = 0; j < a; j++){ int w; cin >> w; aw[i].push_back(w); } } vec<int> dp(m + 1, 0); for(int i = 0; i < n; i++){ for(int j = m; j >= 0; j--){ for(int k = 0; k < aw[i].size(); k++){ if(aw[i][k] <= j){ dp[j] = max(dp[j], dp[j - aw[i][k]] + av[i][k]); } } } } cout << dp[m] << '\n';
} signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin >> t; while(t--){ solve(); } return 0;
}