【背包型动态规划】灵魂分流药剂(soultap) 解题报告

问题来源

BYVoid魔兽世界模拟赛

【问题描述】

皇家炼金师赫布瑞姆刚刚发明了一种用来折磨一切生物的新产品，灵魂分流药剂。灵魂分流药剂的妙处在于能够给服用者带来巨大的痛苦，但是却不会让服用者死去，而且可以阻止服用者的自杀。用它来对付敢于反对希尔瓦娜斯女王的狂徒们，简直是太精妙了。最近，侦察兵抓获了一个来自暴风城的人类探子，希尔瓦娜斯女王命令你用最痛苦的手段来折磨他。
你拥有N瓶药剂，按照成分配比的不同装在M个箱子中。每瓶药剂的有以下参数：对服用者造成的肉体伤害w，精神伤害v，所属的箱子t，和对服用者造成的痛苦程度p。人类探子的生命值为A，意志力为B。你只能从每个箱子中最多拿取1瓶药剂喂给他。注意，喂给他的药剂造成的总肉体伤害不能超过他的生命值A，否则他会死去，总的精神伤害不能超过他的意志力B，否则他会精神崩溃，我们没有必要给一个精神崩溃的傻瓜制造那么多痛苦。在不让他死去而且没有精神崩溃的前提下，你要尽可能给他制造更多的痛苦。这是女王的命令，如果你敢以任何理由或原因没有完成，你的下场就和他一样！

【输入格式】

第1行：四个整数N,M,A,B，M个箱子的编号为1..M。
第2行至第N+1行：第i+1行四个整数w,v,t,p表示第i瓶药剂的肉体伤害，精神伤害，所属箱子的编号，和造成的痛苦值。

【输出格式】

第1行：一个整数，表示能够造成的最大的痛苦值。

【输入样例】

【输出样例】

【数据说明】

对于30%的数据
N<=30
M<=5

对于100%的数据
N<=100
M<=10
A,B<=100

分析

经典的二维费用分组背包，自行百度背包九讲，里面讲得很好，我也不再赘述了。下面是代码

 1 /*
 2 ID: ringxu97
 3 LANG: C++
 4 TASK: soultap
 5 SOLUTION: 多费用分组背包 
 6 */
 7 #include<cstdio>
 8 #include<cstring>
 9 #include<iostream>
10 #include<cmath>
11 #include<cstdlib>
12 #include<algorithm>
13 #include<vector>
14 #include<stack>
15 #include<queue>
16 using namespace std;
17 const int maxn=100+10;
18 const int maxt=10+5;
19 struct DRUG//定义药剂 
20 {
21     int w,v,p;
22     DRUG(int w,int v,int p){w=w;v=v;p=p;}
23     DRUG(){w=v=p=0;}
24 }D[maxt][maxn];//D[i][j]表示第i个箱子里的第j种药 
25 DRUG *P[maxt];//P[i]表示第i个箱子最后一种药剂的后一个位置的指针 
26 
27 int N,M,A,B;//题中变量 
28 void init()//初始化P数组 
29 {
30     for(int i=1;i<=M;++i)
31     {
32         P[i]=D[i];
33     }
34 }
35 void adddurg(int w,int v,int t,int p)//向D[][]中加入新的药 
36 {
37     DRUG *&tmp=P[t]; //获得指针 
38     tmp->w=w;tmp->v=v;tmp->p=p;//加入药品 
39     ++tmp;//后移指针 
40     return;
41 }
42 void read()//读入 
43 {
44     scanf("%d%d%d%d",&N,&M,&A,&B);
45     init();
46     for(int i=1;i<=N;++i)
47     {
48         int w,v,t,p;
49         scanf("%d%d%d%d",&w,&v,&t,&p);
50         adddurg(w,v,t,p);
51     }
52 }
53 int F[maxn][maxn];//F[k][i][j]处理到第k个箱子,w总和<=i,v总和<=j时的最大p(这里省去了第一维) 
54 void Pack()//进行DP 
55 {
56     memset(F,0,sizeof(F));
57     for(int k=1;k<=M;++k)
58     for(int i=A;i>=0;--i)
59     for(int j=B;j>=0;--j)
60     for(DRUG *l=D[k];l<P[k];++l)//注意这里的顺序与01背包不一样，要细细理解(顺序保证了每组物品只选一个或不选) 
61     if(i>=l->w && j>=l->v)
62     {
63         F[i][j]=max(F[i][j],F[i-l->w][j-l->v]+l->p);
64     }
65 }
66 void print(){printf("%d
",F[A][B]);}//打印 
67 int main()
68 {
69     freopen("soultap.in", "r", stdin);
70     freopen("soultap.out", "w", stdout);
71     read();
72     Pack();
73     print();
74     return 0;
75 }

View Code