题解 | #xinjun与阴阳师#

思路

这是一个分组背包的模板题，套一下下面的板吧！
for 所有的组
----for k=体力 k>0
-------- for 这个组的操作
------------ dp递推式

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t,n,m,a[maxn],v[maxn][maxn],w[maxn][maxn],dp[maxn];
    cin>>t;
    while(t--){
        memset(dp,0,sizeof(dp));
        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];
        }
        for(int i=1;i<=n;i++){
            for(int k=m;k>=0;k--){
                for(int j=1;j<=a[i];j++){
                    if(k>=w[i][j]) dp[k]=max(dp[k],dp[k-w[i][j]]+v[i][j]);
                }
            }
        }
        cout<<dp[m]<<endl;
    }
    return 0;
}