牛客 xinjun与阴阳师（背包问题）

背包问题）"/>

牛客 xinjun与阴阳师（背包问题）

题意都是中文的，没啥好说的。

做法：显然是01背包问题，但不过由于是n种方案，每一种方案中只能选一个，加上数据量不是很大，直接三重循环，是可以接受的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
int w[1010][1010],v[1010][1010];
int dp[1010],a[1010];
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T,n,m;cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];for(int j=1;j<=a[i];j++)cin>>v[i][j];for(int j=1;j<=a[i];j++)cin>>w[i][j];}memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){for(int j=m;j>=0;j--){for(int 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;
}