# 1354 - Rubiks

452 次提交 102 次通过

```4 10
4 5 3 6
1 2 100 200
1
2 1 2 330```

333

```#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <stdio.h>

using namespace std;
int v;
int w;
int v2;
int w2;
int dp;
int bp;
int tag;
int b;
int n,m;
int g;
int s,sv;
int a;
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
scanf("%d",&g);
memset(tag,0,sizeof(tag));
for(int i=1;i<=g;i++)
{
scanf("%d",&s[i]);
int value=0;int weight=0;
for(int j=1;j<=s[i];j++)
{
scanf("%d",&b[i][j]);
tag[b[i][j]]=i;
value+=v[b[i][j]];
weight+=w[b[i][j]];
}
scanf("%d",&a);
value+=a;
w2[i]=weight;
v2[i]=value;
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
if(!tag[i])
{
for(int j=m;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
for(int i=1;i<=g;i++)
{
memcpy(bp, dp, sizeof(dp));
for(int j=m;j>=w2[i];j--)
bp[j]=max(bp[j],bp[j-w2[i]]+v2[i]);
for(int k=1;k<=s[i];k++)
{
for(int j=m;j>=w[b[i][k]];j--)
dp[j]=max(dp[j],dp[j-w[b[i][k]]]+v[b[i][k]]);
}
for(int j=1;j<=m;j++)
dp[j]=max(dp[j],bp[j]);

}
printf("%d\n",dp[m]);
}
return 0;
}```

481 篇文章43 人订阅

### 我来说两句

0 条评论 