Diablo Items
【题目描述】
Diablo II中，有两种物品：普通物品和魔法物品。显然，魔法物品有普通物品没有的神奇力量。
魔法物品和普通物品都可以被卖掉：一个普通物品只有一个价值Pi；而一个魔法物品有两个价值Pi1和Pi2，当使用购买的魔法卷轴鉴定过这个魔法物品以后，它的价值就变为Pi2，否则它只具有Pi1的价值（当然Pi2一定要大于Pi1）。鉴定一个魔法物品需要花费Q来购买一个魔法卷轴，每个魔法卷轴只能使用一次。
你的手中有一些物品。对于普通物品，你已经知道了它们的价值Pi；对于魔法物品，你已经知道了它们的价值Pi1和Pi2。
现在，你想要把它们全部卖掉，以得到最大的收益。
注意：
1. 开始时，你的收中没有钱，无法购买卷轴。
2. 开始时，没有任何魔法物品被卷轴鉴定过。
3. 如果你的手中有足够多的钱，你可以购买足够多的卷轴，但你手中的剩余的钱不能为负。
【输入格式】
每个测试点有多组测试数据：
对于每组测试数据：
第一行两个整数N和Q，N表示拥有物品的数量，Q表示购买一个魔法卷轴的花费。
第二行..第N+1行每行有一个整数或两个整数，如果为一个数，表示这件物品是普通物品，价值为Pi，否则为魔法物品两个价值为Pi1和Pi2。
【输出格式】
对于每组测试数据：
一个整数，即最大的收益。
【样例输入】
2 10
5
8
2 10
10
10 100
【样例输出】
13
100
【数据范围】
0<=N<=1000
Q<=30000
Pi<=10000
Pi1<Pi2<=10000
首先将普通物品和 pi2-pi1-q<0 的魔法物品卖了。
然后如果可以买得起卷轴，就都买了卷轴，然后卖魔法物品。（显然，pi2>q ，所以再卖魔法物品的时候，手里的钱会越来越多）
如果买不起的话，就用背满包判断卖哪些未鉴定的物品。
var
a:array[0..1000,0..2] of longint;
f:array[0..10000] of longint;
cost,n,m,q:longint;
procedure init;
var
i,x,y:longint;
s,t:string;
begin
m:=0;
cost:=0;
readln(n,q);
for i:=1 to n do
begin
readln(s);
if (pos(' ',s)=0) then
begin
val(s,x);
inc(cost,x);
end
else
begin
t:=copy(s,pos(' ',s)+1,length(s)-pos(' ',s));
s:=copy(s,1,pos(' ',s)-1);
val(t,x);
val(s,y);
if (x-q<y) then inc(cost,y)
else
begin
inc(m);
a[m][0]:=x;
a[m][1]:=y;
a[m][2]:=x-y-q;
end;
end;
end;
end;
function min(a,b:longint):longint;
begin
if (a<0) then exit(b);
if (b<0) then exit(a);
if (a<b) then exit(a) else exit(b);
end;
function run:longint;
var
sum,need,next,i,j:longint;
begin
sum:=0;
if (cost>=q) or (m=0) then
begin
sum:=cost;
for i:=1 to m do
inc(sum,a[i][0]-q);
exit(sum);
end;
need:=q-cost;
fillchar(f,sizeof(f),255);
f[0]:=0;
for i:=1 to m do
for j:=need downto 0 do
begin
if (f[j]<>-1) then
begin
next:=j+a[i][1];
next:=min(next,need);
f[next]:=min(f[next],f[j]+a[i][2]); //可以更新，则是卖鉴定后的物品，背满包。
end;
end;
if (f[need]=-1) then
begin
sum:=cost;
for i:=1 to m do
inc(sum,a[i][1]);
exit(sum); //物品全卖了也不够买卷轴的
end
else
begin
sum:=cost;
for i:=1 to m do
inc(sum,a[i][0]-q); //先不管一开始买卷轴的“贷款”
exit(sum-f[need]); //将“贷款”减去
end;
end;
begin
assign(input,'items.in');reset(input);
assign(output,'items.out');rewrite(output);
while (not eof) do
begin
init;
writeln(run);
end;
close(input);
close(output);
end.