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

链接：https://ac.nowcoder.com/acm/problem/14602
来源：牛客网

题目描述：

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

输入描述：

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

输出描述：

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

输入

1
3 10
2
2 3
3 2
2
1 1
3 4
1
5
5

输出

9

这道题本质上还是01背包问题，只不过在此基础上又增加了一重循环（a[i]），多读几遍题目，把输入的数据先给屡清楚，只要输入的数据顺序懂了，那么按照01背包的思路去解就可以了，在此我推一下之前写的01背包模板题思路：01背包问题（动态规划）+一维数组的优化

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int a[1010],v[1010][1010],w[1010][1010];
int dp[1010];
int main(){
	int t,n,m,i,j,k;
	cin>>t;//t组数据
	while(t--){
		memset(dp,0,sizeof(dp));//每次输入前先重置dp[]，v[]和w[]没有必要重置
		cin>>n>>m;//n个模式，m点体力
		for(i=1;i<=n;i++){
			cin>>a[i];//每个模式下有a[i]种操作
			for(j=1;j<=a[i];j++){
				cin>>v[i][j];//收益
			}
			for(j=1;j<=a[i];j++){
				cin>>w[i][j];//消耗的体力
			}
		}//-------------------以上是输入的数据-----------------
		//三重循环，思路还是01背包的思路
		for(i=1;i<=n;i++){//遍历n中模式
			for(j=m;j>=0;j--){//体力倒序遍历（01背包优化）
				for(k=1;k<=a[i];k++){//遍历收益和体力
					if(j>=w[i][k]){
						dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);//状态转移方程
					}
				}
			}
		}
		cout<<dp[m]<<endl;
	}
	return 0;
}