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.

Download