[nssl 1317] 灵魂分流药剂 {背包变形}

[nssl 1317] 灵魂分流药剂 {背包变形}

题目

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

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

解题思路

令 f ( i , j , k ) 表 示 当 服 用 者 拥 有 i 的 生 命 值 、 j 的 意 志 力 ， 且 只 用 前 k 个 箱 子 的 药 剂 时 所 造 成 的 最 大 痛 苦 值 。 令f(i,j,k)表示当服用者拥有i的生命值、j的意志力，且只用前k个箱子的药剂时所造成的最大痛苦值。 令f(i,j,k)表示当服用者拥有i的生命值、j的意志力，且只用前k个箱子的药剂时所造成的最大痛苦值。
状 态 转 移 方 程 为 ： f ( i , j , k ) = m a x ( m a x ( f ( i − w [ k ] [ m ] , j − v [ k ] [ m ] , k − 1 ) ) + p [ k ] [ m ] , f ( i , j , k − 1 ) ) 状态转移方程为：f(i,j,k)=max(max( f(i-w[k][m] , j-v[k][m] ,k-1) )+p[k][m] , f(i,j,k-1) ) 状态转移方程为：f(i,j,k)=max(max(f(i−w[k][m],j−v[k][m],k−1))+p[k][m],f(i,j,k−1))
（ m = 1.. 第 k 组 的 药 剂 数 ， 并 且 保 证 0 &lt; = i − w [ k ] [ m ] 且 0 &lt; = j − v [ k ] [ m ] ） （m=1..第k组的药剂数，并且保证0&lt;=i-w[k][m] 且 0&lt;=j-v[k][m]） （m=1..第k组的药剂数，并且保证0<=i−w[k][m]且0<=j−v[k][m]）
其 中 w [ k ] [ m ] 与 v [ k ] [ m ] 分 别 表 示 第 k 个 箱 子 的 第 m 瓶 药 剂 的 肉 体 折 磨 与 精 神 折 磨 其中w[k][m]与v[k][m]分别表示第k个箱子的第m瓶药剂的肉体折磨与精神折磨 其中w[k][m]与v[k][m]分别表示第k个箱子的第m瓶药剂的肉体折磨与精神折磨

代码

#include<cstdio>
#include<algorithm>
#define rep(i,x,y) for (register int i=x;i<=y;++i)
using namespace std; 
int n,m,sa,sb,w[101][101],v[101][101],t[101],p[101][101],ans,s[101],f[101][101][101]; 
int main(){scanf("%d%d%d%d",&n,&m,&sa,&sb); rep(i,1,n){int x,y,pp; scanf("%d%d%d%d",&x,&y,&t[i],&pp); s[t[i]]++; w[t[i]][s[t[i]]]=x; v[t[i]][s[t[i]]]=y; p[t[i]][s[t[i]]]=pp; }rep(q,1,sa) rep(g,1,sb)	rep(i,1,m) {int tb=0; rep(j,1,s[i]) if (q>=w[i][j]&&g>=v[i][j]) tb=max(tb,f[q-w[i][j]][g-v[i][j]][i-1]+p[i][j]); f[q][g][i]=max(tb,f[q][g][i-1]); }printf("%d",f[sa][sb][m]); 
}