比赛 20101116 评测结果 AAAAAWWWWA
题目名称 打砖块 最终得分 60
用户昵称 donny 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-11-16 10:17:22
显示代码纯文本
program gamea;
var
  i,j,l:longint;
  n,m,k:longint;
  a,z:array[1..200,1..200]of longint;
  x:array[1..200,1..2]of longint;
  b,bb:array[1..200,1..200,1..2]of longint;
  f:array[-1..200,-1..200]of longint;
  c:char;
function max(const x,y:longint):longint;
begin
  if x>y then exit(x)
  else exit(y);
end;
begin
  assign(input,'gamea.in');
  reset(input);
  assign(output,'gamea.out');
  rewrite(output);
  readln(n,m,k);
  for i:=1 to n do
  begin
    for j:=1 to m do
    begin
      read(a[i,j],c);
      read(c);
      if c='N' then z[i,j]:=1 else z[i,j]:=0;
    end;
    readln;
  end;
  for i:=n-1 downto 1 do
    for j:=1 to m do
    begin
      a[i,j]:=a[i,j]+a[i+1,j];
      z[i,j]:=z[i,j]+z[i+1,j];
    end;
  for i:=1 to m do
  begin
    x[i,1]:=z[1,i];
    x[i,2]:=i;
  end;
  for i:=1 to m-1 do
    for j:=i+1 to m do
      if x[j,1]<x[i,1] then
      begin
        l:=x[j,1];
        x[j,1]:=x[i,1];
        x[i,1]:=l;
        l:=x[j,2];
        x[j,2]:=x[i,2];
        x[i,2]:=l;
      end;
  for i:=n downto 1 do
    for j:=1 to m do
    begin
      if bb[j,z[i,j],1]=0 then
      bb[j,z[i,j],1]:=a[i,j]
      else
      bb[j,z[i,j],2]:=a[i,j];
    end;
  for i:=1 to m do
    for j:=1 to n do
    begin
      b[i,j,1]:=bb[x[i,2],j,1];
      b[i,j,2]:=bb[x[i,2],j,2];
    end;
  for i:=1 to m do
  begin
    j:=0;
    repeat
      inc(j);
      if b[i,j,1]=0 then
        b[i,j,1]:=a[1,x[i,2]];
    until j=k;
  end;
  for j:=1 to m do
    for i:=0 to k do
    begin
      f[j,i]:=max(f[j-1,i],f[j,i-1]);
      if i<>k then
      begin
        for l:=1 to i do
          if f[j-1,i-l]+max(b[j,l,1],b[j,l,2])>f[j,i] then
            f[j,i]:=f[j-1,i-l]+max(b[j,l,1],b[j,l,2]);
      end
      else
      begin
        for l:=1 to i do
          if f[j-1,i-l]+b[j,l,1]>f[j,i] then
            f[j,i]:=f[j-1,i-l]+b[j,l,1];
      end;
    end;
  writeln(f[m,k]);
  close(input);
  close(output);
end.