1084: [SCOI2005]最大子矩阵
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1325 Solved: 670
[Submit][Status]
Description
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。
Input
第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
Output
只有一行为k个子矩阵分值之和最大为多少。
Sample Input
3 2 2
1 -3
2 3
-2 3
1 -3
2 3
-2 3
Sample Output
9
HINT
Source
题解：看了半天不知道怎么办才好，直到发现M<=2（HansBug:呵呵你早说就俩列得了呗呵呵哒）假如这样的话那么直接根据此行俩数的不同情况讨论下不就得啦。。。情况繁一点
program bzoj1084;
{$mode objfpc}{$H+}
uses
Classes, SysUtils
{ you can add units after this };
var
i,j,k,l,m,n,tot,ii,jj:longint;
b:array [..,..] of longint;
a:array [..,..,..] of longint;
begin
readln(n,m,k);
for i:= to n do for j:= to m do read(b[i,j]);
if m= then
begin
for i:= to k do
begin
a[,,i]:=-maxlongint div ;
a[,,i]:=-maxlongint div ;
end;
a[,,]:=;
for i:= to n do
for j:= to k do
begin
if a[i-,,j]>a[i-,,j] then a[i,,j]:=a[i-,,j] else a[i,,j]:=a[i-,,j];
if j= then
a[i,,j]:=-maxlongint div
else
begin
a[i,,j]:=a[i-,,j]+b[i,];
if a[i,,j]<a[i-,,j-]+b[i,] then a[i,,j]:=a[i-,,j-]+b[i,];
if (j>) and (a[i,,j]<a[i-,,j-]+b[i,]) then a[i,,j]:=a[i-,,j-]+b[i,];
end;
end;
if a[n,,k]>a[n,,k] then writeln(a[n,,k]) else writeln(a[n,,k]);
halt;
end;
for i:= to k do for j:= to do a[,j,i]:=-maxlongint div ;
a[,,]:=;
for i:= to n do
for j:= to k do
begin
for ii:= to do
case ii of
:begin
a[i,,j]:=a[i-,,j];
for jj:= to do if a[i,,j]<a[i-,jj,j] then a[i,,j]:=a[i-,jj,j];
end;
..:begin
a[i,ii,j]:=a[i-,ii,j]+b[i,ii];
for jj:= to do if (j>) and (a[i,ii,j]<a[i-,jj,j-]+b[i,ii]) then a[i,ii,j]:=a[i-,jj,j-]+b[i,ii];
if a[i,ii,j]<a[i-,,j]+b[i,ii] then a[i,ii,j]:=a[i-,,j]+b[i,ii];
end;
:begin
a[i,ii,j]:=a[i-,ii,j]+b[i,]+b[i,];
for jj:= to do if (j>=) and (a[i,ii,j]<a[i-,jj,j-]+b[i,]+b[i,]) then a[i,ii,j]:=a[i-,jj,j-]+b[i,]+b[i,];
for jj:= to do if (j>=) and (a[i,ii,j]<a[i-,jj,j-]+b[i,]+b[i,]) then a[i,ii,j]:=a[i-,jj,j-]+b[i,]+b[i,];
end;
:begin
a[i,ii,j]:=a[i-,ii,j]+b[i,]+b[i,];
for jj:= to do if (j>=) and (a[i,ii,j]<a[i-,jj,j-]+b[i,]+b[i,]) then a[i,ii,j]:=a[i-,jj,j-]+b[i,]+b[i,];
end;
end;
end;
tot:=-maxlongint div ;
for i:= to do if tot<a[n,i,k] then tot:=a[n,i,k];
writeln(tot);
end.