TRIBE - Bộ lạc

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
program TRIBE;
const
  FINP='';
  FOUT='';
  MAXN=52;
type
  st=string[MAXN];
var
  a,b,c,n:longint;
  cost,sa,sb:array[1..MAXN] of longint;
  word:array[1..MAXN] of st;
  pre,d:array[0..MAXN,0..MAXN,0..MAXN] of longint;
procedure inp;
var
  ch:char;
  f:text;
  i,j:longint;
begin
  assign(f,FINP); reset(f);
  readln(f,n);
  readln(f,a,b,c);
  for i:=1 to n do
    begin
      repeat
        read(f,ch);
        if ch<>' 'then word[i]:=word[i]+ch;
        if ch='a' then inc(sa[i])
        else if ch='b' then inc(sb[i]);
      until ch=' ';
      readln(f,cost[i]);
    end;
  close(f);
end;
procedure init;
var
  i:longint;
begin
  for i:=1 to MAXN do
    begin
      word[i]:='';
      sa[i]:=0; sb[i]:=0;
      cost[i]:=0;
    end;
end;
procedure solve;
var
  i,aa,bb,u:longint;
begin
  for i:=1 to c+1 do
  begin
    for u:=1 to n do
    for aa:=0 to a do
    for bb:=0 to b do
      if (aa>=sa[u]) and (bb>=sb[u]) then
        if d[i,aa,bb]<d[i-1,aa-sa[u],bb-sb[u]]+cost[u] then
          begin
            d[i,aa,bb]:=d[i-1,aa-sa[u],bb-sb[u]]+cost[u];
            pre[i,aa,bb]:=u;
          end;
  end;
end;
procedure ans;
var
  f:text;
  i,aa,bb,li,la,lb:longint;
  procedure trace(i,a,b:longint);
  var
    u:longint;
  begin
    u:=pre[i,a,b];
    if u=0 then exit;
    write(f,word[u]);
    if i<li+1 then write(f,' ');
    if i>1 then trace(i-1,a-sa[u],b-sb[u]);
  end;
begin
  assign(f,FOUT); rewrite(f);
  li:=0; la:=0; lb:=0;
  for i:=c+1 downto 1 do
  for aa:=0 to a do
  for bb:=0 to b do
    if d[i,aa,bb]>d[li,la,lb] then
      begin
        li:=i;
        la:=aa;
        lb:=bb;
      end;
  if li>0 then trace(li,la,lb);
  close(f);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure swaps(var a,b:st);
var
  temp:st;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint);
var
  i,j:longint;
  mid:st;
begin
  mid:=word[(l+r) div 2];
  i:=l; j:=r;
  repeat
    while word[i]<mid do inc(i);
    while word[j]>mid do dec(j);
    if i<=j then
      begin
        swaps(word[i],word[j]);
        swap(sa[i],sa[j]);
        swap(sb[i],sb[j]);
        swap(cost[i],cost[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
begin
  init;
  inp;
  sort(1,n);
  solve;
  ans;
end.

Download