牛客 xinjun与阴阳师（01背包）

背包）"/>

牛客 xinjun与阴阳师（01背包）

题目链接： xinjun与阴阳师

大致题意:

初始体力为m，有n种模式，每种模式对应a[i]个操作，分别给出每个操作需要耗费的体力和得到的收益，要求每种模式每日只能选一个操作，问收益最大是多少

解题思路:

01背包

AC代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int f[N];
int a[N], w[N][N], v[N][N];
int main() {int t; cin >> t;while (t--) {memset(f, 0, sizeof f);cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> a[i];for (int j = 1; j <= a[i]; ++j) //体力cin >> w[i][j];for (int j = 1; j <= a[i]; ++j) //价值cin >> v[i][j];}for (int i = 1; i <= n; ++i)for (int j = m; j >= 0; --j)for (int k = 1; k <= a[i]; ++k)if (j >= v[i][k])f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);cout << f[m] << endl;}return 0;
}

END