[BYVoid S1] 灵魂分流药剂

发表于 | 分类于 | | 浏览 次
字数统计: 887 个 | 阅读时长 ≈ 4 分

题面

幽暗城皇家炼金师赫布瑞姆刚刚发明了一种用来折磨战俘的新型药 剂，这种药剂被称为灵魂分流药剂。灵魂分流药剂的妙处在于能够给战俘带来巨大的痛苦，但是却不会让战俘死去。这种药剂中包含了一些治疗的成分，所以即使战 俘想自尽，也会被救活。用这种求生不得，求死不能的感觉，来对付反对希尔瓦娜斯女王的狂徒们，实在是太美妙了。当然，灵魂分流药剂要限定在一个用量范围之 内，过少会达不到效果，而过多会直接杀了战俘。

最近，我们抓获了一个来自暴风城的探子，他掌握了我们的许多重要情报。希尔瓦娜斯女王命令你用最痛苦的手段折磨他。你从你的导师，灵魂分流药剂的发明者——皇家炼金师赫布瑞姆那里获得了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行：一个整数，表示能够造成的最大的痛苦值。

样例

input

1
2
3
4
5
6
5 3 20 20
5 10 1 200
10 5 1 100
8 11 2 56
10 10 2 50
5 5 3 100

output

1
300

数据规模

对于30%的数据

N<=30

M<=5

对于100%的数据

N<=100

M<=10

A,B<=100

思路

裸的二维背包。。注意数据格式

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# include <bits/stdc++.h>
using namespace std;
 
inline char getc() { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
 
inline int gn() { 
    register int k = 0, f = 1;
    register char c = getc();
    for(; !isdigit(c); c = getc()) if (c == '-') f = -1;
    for(; isdigit(c); c = getc()) k = k * 10 + c - '0';
    return k * f;
}
 
int f[102][102][102], n, m, a, b, w[102], v[102], p[102], ans;
vector <int> box[12];
 
int main() { 
# ifndef LOCAL
    freopen("soultap.in", "r", stdin);
    freopen("soultap.out", "w", stdout);
# else 
    freopen("in", "r", stdin);
# endif
    n = gn(), m = gn(), a = gn(), b = gn();
    for(int t, i = 1; i <= n; i++) { 
        w[i] = gn(), v[i] = gn(), t = gn(), p[i] = gn();
        box[t].push_back(i);
    }
    for(int i = 1; i <= m; i++) { 
        for(int j = 0; j <= a; j++) { 
            for(int k = 0; k <= b; k++) { 
                f[i][j][k] = f[i - 1][j][k];
            }
        }
        for(int o = 0; o < box[i].size(); o++) { 
            int tmp = box[i][o];
            for(int j = w[tmp]; j <= a; j++) { 
                for(int k = v[tmp]; k <= b; k++) { 
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j - w[tmp]][k - v[tmp]] + p[tmp]);
                    ans = max(ans, f[i][j][k]);
                }
            }
        }
    }
    printf("%d\n", ans);
}