HUST 1354 - Rubiks (DP)
1354 - Rubiks
时间限制：1秒 内存限制：64兆
452 次提交 102 次通过
题目描述 Isun is a genius. Not only he is an expert in algorithm, but also he plays damn-good in many funny games. Besides, he can recover a Rubik in 16 seconds or even less. The man is very crazy about Rubiks, and he has bought a lot of Rubiks. As we know, there are so many kinds of Rubiks in the world. Isun wants to buy the most valuable ones with his limited money. There are N kinds of Rubiks in all. Each of them has a price Pi(1<=i<=N) RMB and a value Vi(1<=i<=N). Isun will pay no more than M (RMB) in total. In addition, there are some Rubik families like “甲X” or “封X”. And a kind of Rubik belongs to one family at most. If Isun buys a group of them, the value of them as a family will increase. Can you get the largest value of the Rubiks that Isun can get with M (RMB). (Isun just buy one Rubik each kind at most) 输入 The input contains several test cases and is ended by EOF. Each test case begins with two integers: N (1<=N<=1000) and M (1<=M<=10000). The second line contains N integers representing the prices of the Rubiks. (1<=Pi<=10000) The third line contains N integers representing the value of the Rubiks. (1<=Vi<=10000) Then a line contains an integer G(0<=G<=15) representing the number of the Rubik families. Next G lines each with a start of an integer Si(1<=Si<=N) representing the number of Rubiks in the ith family. The following Si integers represent Rubik’s id (which start from 1 to N). And an integer Yi at the end means the value increased if you buy them all.(1<=Yi<=10000) 输出 There should be one line per test case containing the largest value. 样例输入
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[1020];
int w[1020];
int v2[20];
int w2[20];
int dp[10005];
int bp[10005];
int tag[1005];
int b[20][1005];
int n,m;
int g;
int s[20],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;
}