题目链接:题目
大意:
有一定体力,有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;
}