「NOIP模拟赛」灵魂分流药剂
问题描述
皇家炼金师赫布瑞姆刚刚发明了一种用来折磨一切生物的新产品，灵魂分流药剂。灵魂分流药剂的妙处在于能够给服用者带来巨大的痛苦，但是却不会让服用者死去，而且可以阻止服用者的自杀。用它来对付敢于反对希尔瓦娜斯女王的狂徒们，简直是太精妙了。最近，侦察兵抓获了一个来自暴风城的人类探子，希尔瓦娜斯女王命令你用最痛苦的手段来折磨他。
你拥有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
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; int n,m,a,b,ans; int s[11][101],w[101],v[101],p[101],f[101][101]; int main() { //freopen("soultap.in","r",stdin); //freopen("soultap.out","w",stdout); scanf("%d%d%d%d",&n,&m,&a,&b); for(int i=1;i<=n;i++) { int t; scanf("%d%d%d%d",&w[i],&v[i],&t,&p[i]); s[t][0]++; s[t][s[t][0]]=i; } for(int k=1;k<=m;k++) for(int i=a;i>0;i--) for(int j=b;j>0;j--) for(int l=1;l<=s[k][0];l++) { int t=s[k][l]; if(i<w[t]||j<v[t])continue; f[i][j]=max(f[i][j],f[i-w[t]][j-v[t]]+p[t]); if(f[i][j]>ans)ans=f[i][j]; } printf("%d",ans); return 0; } |
计数器 9774466
OI 课件=>
OI 课件=>
二维费用的多重背包水题。。。