比赛 20101116 评测结果 AAAAWWWWWA
题目名称 打砖块 最终得分 50
用户昵称 ybh 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-11-16 11:06:04
显示代码纯文本
{砖
 动态规划 泛化物品 背包问题
 Author: yangbohua
 Time: 2010-11-16 11:10}

program gamea;
var
  a,p:array[0..201,0..201] of longint;
  g:array[0..201,0..201] of int64;
  b:array[0..201,0..201] of boolean;
  f:array[0..201] of int64;
  n,m,kk,i,j,k:longint;
  r:char;

begin
  assign(input,'gamea.in');
  reset(input);
  assign(output,'gamea.out');
  rewrite(output);

  readln(n,m,kk);
  if kk=0 then
  begin
    writeln(0);
    close(input);
    close(output);
    halt;
  end;
  for i:=1 to n do
  begin
    for j:=1 to m do
    begin
      read(a[i,j]);
      read(r);
      while (r<>'Y') and (r<>'N') do
        read(r);
      if r='Y'
        then b[i,j]:=true
        else b[i,j]:=false;
    end;
    readln;
  end;

  for i:=1 to m do
  begin
    k:=0;
    for j:=n downto 1 do
      if b[j,i] then
      begin
        g[i,k]:=g[i,k]+a[j,i];
        p[i,k]:=j;
      end
      else
      begin
        k:=k+1;
        if k>kk then break;
        g[i,k]:=g[i,k-1]+a[j,i];
        p[i,k]:=j;
      end;
  end;

  for i:=1 to m do
    for k:=kk downto 0 do
      for j:=0 to k do
        if (k>j) or (k=0) then
        begin
          if f[k-j]+g[i,j]>f[k]
            then f[k]:=f[k-j]+g[i,j];
        end
        else
        begin
          if k=j then
          begin
            if b[p[i,j],i] then
            begin
              if f[0]+g[i,j]-a[p[i,j],i]>f[k]
                then f[k]:=f[0]+g[i,j]-a[p[i,j],i];
            end
            else
              if f[0]+g[i,j]>f[k]
                then f[k]:=f[0]+g[i,j];
          end
        end;

  writeln(f[kk]);
  close(input);
  close(output)
end.