比赛 |
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.