【NOIP模拟赛】灵魂分流药剂

2014年3月7日1,1241

问题描述

皇家炼金师赫布瑞姆刚刚发明了一种用来折磨一切生物的新产品,灵魂分流药剂。灵魂分流药剂的妙处在于能够给服用者带来巨大的痛苦,但是却不会让服用者死去,而且可以阻止服用者的自杀。用它来对付敢于反对希尔瓦娜斯女王的狂徒们,简直是太精妙了。最近,侦察兵抓获了一个来自暴风城的人类探子,希尔瓦娜斯女王命令你用最痛苦的手段来折磨他。

 

你拥有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行:一个整数,表示能够造成的最大的痛苦值。

 

样例输入

5 3 20 20

5 10 1 200

10 5 1 100

8 11 2 56

10 10 2 50

5 5 3 100

 

样例输出

300

 

数据规模

对于30%的数据

N<=30

M<=5

 

对于100%的数据

N<=100

M<=10

A,B<=100

 

  • zjq2017年4月28日 下午1:11 回复

    二维费用的多重背包水题。。。

    #1