题解 | #xinjun与阴阳师#

0/1背包问题； 一维可以看看其他大佬的代码；
如果是用二维结构写的，那一定要注意将上一轮的状态更新到这一轮；

using namespace std;
const int N = 1010,M = 1010;
int w[N][M],v[N][M],a[N],f[N][N];
void solve()
{
    int n,m;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(f,0,sizeof(f));
    //前i个模式中花费了j体力
    for(int i = 1;i <= n; i++){
    	for(int j = 0;j <= m; j++){
        	f[i][j] = f[i-1][j];//复制上一轮状态,或者直接让k从0开始
    		for(int k = 1;k <= a[i]; k++){//操作k 
    			if(j >= w[i][k]){
    				f[i][j] = max(f[i][j],f[i-1][j-w[i][k]]+v[i][k]);
				}
			}
		}
    }
    cout<<f[n][m]<<'\n';
}
int main()
{
    int i,j;
    int t;cin>>t; 
    while(t--) solve();
    return 0;
}