【牛客-14602】xinjun与阴阳师（01背包）

【牛客-14602】xinjun与阴阳师（01背包） - Sky丨Star

sky-stars 2019-05-30 原文

xinjun是各类手游的狂热粉丝，因随手一氪、一氪上千而威震工大，现在他迷上了阴阳师。xinjun玩手游有一个习惯，就是经过层层计算制定出一套方案来使操作利益最大化(因此即使有扫荡券也不用，故称圣雄肝帝)。已知阴阳师有N个模式可以操作，模式i有a_i种操作，但每种模式每日只能选用一种操作，可以不选。操作j能收益v_j，但需要花费体力w_j点。xinjun每日拥有体力M点，求他每日最多能得到多少收益。

输入描述:

第一行一个正整数T(T<=10)，表示共有T组数据。对于每组数据，第一行两个正整数N，M(1<=N，M<=1000)。接下来N段数据，每段第一行一个正整数a_i(1<=a_i<=1000)，第二行a_i个正整数v_j(1<=v_j<=1000)，第三行a_i个正整数w_j(1<=w_j<=1000)。每组数据a_i之和不大于10⁴。

输出描述：

对每组数据输出一行，即xinjun每日最多能得到多少收益。

输入

1

3 10

2

2 3

3 2

2

1 1

3 4

1

5

5

输出

9

题目链接：

https://ac.nowcoder.com/acm/problem/14602（先注册）

变形的01背包，只要用vector存收益v_j，和花费体力w_{j 。}

AC代码

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <fstream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <deque>
 7 #include <vector>
 8 #include <queue>
 9 #include <string>
10 #include <cstring>
11 #include <map>
12 #include <stack>
13 #include <set>
14 #include <numeric>
15 using namespace std;
16 typedef long long ll;
17 vector<int> v[1005],w[1005];
18 int dp[1005];
19 int n,m;
20 int T;
21 int main()
22 {
23     cin >> T;
24     while(T--)
25     {
26         memset(dp,0,sizeof(dp));
27         cin >> n >> m;
28         //每次初始化vector
29         for(int i=0; i<n; i++)
30         {
31             v[i].clear();
32             w[i].clear();
33         }
34         for(int i=0; i<n; i++)
35         {
36             int a;
37             cin>> a;
38             for(int j=0; j<a; j++)
39             {
40                 int V;
41                 cin >> V;
42                 v[i].push_back(V);
43             }
44             for(int j=0; j<a; j++)
45             {
46                 int W;
47                 cin >> W;
48                 w[i].push_back(W);
49             }
50         }
51         for(int i=0; i<n; i++)
52         {
53             for(int j=m; j>=0; j--)
54             {
55                 for(int k=0; k<v[i].size(); k++)
56                 {
57                     if(j>=w[i][k])
58                     {
59                         dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);//状态转移
60                     }
61                 }
62             }
63         }
64         cout << dp[m] << endl;
65     }
66     return 0;
67 }