当前位置：首页 > article >正文

牛客背包问题练习 xinjun与阴阳师

article 2024/9/21 17:50:45

题目链接：题目

大意：

有一定体力，有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;  
}