TRIBE - Bộ lạc
Tác giả: ladpro98
Ngôn ngữ: Pascal
{$H+}
program TRIBE;
uses math,sysutils;
const maxn=50;
fi='';
type e=record
a,b,w:longint;
s:string;
end;
var f,choose:array[0..maxn,0..maxn,0..maxn] of longint;
n,mx,my,mz,d:longint;
p:array[1..maxn] of e;
procedure input;
var inp:text;
i,j:longint;
s:string;
te:e;
begin
assign(inp,fi);reset(inp);
readln(inp,n);
readln(inp,mx,my,mz);
for i:=1 to n do begin
readln(inp,s);
for j:=1 to length(s) do begin
if s[j] = ' ' then break;
if s[j] = 'a' then inc(p[i].a)
else inc(p[i].b);
end;
p[i].w:=StrToInt(copy(s,j+1,length(s)-j));
p[i].s:=copy(s,1,j-1);
end;
close(inp);
for i:=1 to n do
for j:=i+1 to n do
if p[i].s>p[j].s then begin
te:=p[i];
p[i]:=p[j];
p[j]:=te;
end;
end;
procedure dp;
var i,x,y,z:longint;
begin
for x:=0 to mx do
for y:=0 to my do
for z:=1 to mz+1 do
begin
for i:=1 to n do
if (x>=p[i].a) and (y>=p[i].b) and (f[x,y,z]<f[x-p[i].a,y-p[i].b,z-1]+p[i].w) then begin
f[x,y,z]:=f[x-p[i].a,y-p[i].b,z-1]+p[i].w;
choose[x,y,z]:=i;
end;
end;
end;
procedure output;
var i,x,y,z:longint;
begin
x:=mx;y:=my;z:=mz+1;
while choose[x,y,z]>0 do
begin
d:=choose[x,y,z];
dec(x,p[d].a);
dec(y,p[d].b);
dec(z);
write(p[d].s);
if choose[x,y,z]>0 then write(' ');
end;
end;
begin
input;
dp;
output;
end.