1084: [SCOI2005]最大子矩阵

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

Sample Output

HINT

Source

 1 program bzoj1084;
 2 
 3 {$mode objfpc}{$H+}
 4 
 5 uses
 6   Classes, SysUtils
 7   { you can add units after this };
 8 
 9 var
10     i,j,k,l,m,n,tot,ii,jj:longint;
11     b:array [0..101,0..3] of longint;
12     a:array [0..101,0..4,0..10] of longint;
13 begin
14     readln(n,m,k);
15     for i:=1 to n do for j:=1 to m do read(b[i,j]);
16     if m=1 then
17         begin
18             for i:=0 to k do
19                 begin
20                     a[0,1,i]:=-maxlongint div 10;
21                     a[0,0,i]:=-maxlongint div 10;
22                 end;
23             a[0,0,0]:=0;
24             for i:=1 to n do
25                 for j:=0 to k do
26                     begin
27                         if a[i-1,1,j]>a[i-1,0,j] then a[i,0,j]:=a[i-1,1,j] else a[i,0,j]:=a[i-1,0,j];
28                         if j=0 then
29                            a[i,1,j]:=-maxlongint div 10
30                         else
31                             begin
32                                 a[i,1,j]:=a[i-1,1,j]+b[i,1];
33                                 if a[i,1,j]1,0,j-1]+b[i,1] then a[i,1,j]:=a[i-1,0,j-1]+b[i,1];
34                                 if (j>0) and (a[i,1,j]1,1,j-1]+b[i,1]) then a[i,1,j]:=a[i-1,1,j-1]+b[i,1];
35                             end;
36                     end;
37             if a[n,0,k]>a[n,1,k] then writeln(a[n,0,k]) else writeln(a[n,1,k]);
38             halt;
39         end;
40     for i:=0 to k do for j:=0 to 4 do a[0,j,i]:=-maxlongint div 10;
41     a[0,0,0]:=0;
42     for i:=1 to n do
43         for j:=0 to k do
44             begin
45                 for ii:=0 to 4 do
46                     case ii of
47                          0:begin
48                                 a[i,0,j]:=a[i-1,0,j];
49                                 for jj:=1 to 4 do if a[i,0,j]1,jj,j] then a[i,0,j]:=a[i-1,jj,j];
50                          end;
51                          1..2:begin
52                                    a[i,ii,j]:=a[i-1,ii,j]+b[i,ii];
53                                    for jj:=0 to 4 do if (j>0) and (a[i,ii,j]1,jj,j-1]+b[i,ii]) then a[i,ii,j]:=a[i-1,jj,j-1]+b[i,ii];
54                                    if a[i,ii,j]1,3,j]+b[i,ii] then a[i,ii,j]:=a[i-1,3,j]+b[i,ii];
55                          end;
56                          3:begin
57                                 a[i,ii,j]:=a[i-1,ii,j]+b[i,2]+b[i,1];
58                                 for jj:=0 to 4 do if (j>=2) and (a[i,ii,j]1,jj,j-2]+b[i,2]+b[i,1]) then a[i,ii,j]:=a[i-1,jj,j-2]+b[i,2]+b[i,1];
59                                 for jj:=1 to 3 do if (j>=1) and (a[i,ii,j]1,jj,j-1]+b[i,2]+b[i,1]) then a[i,ii,j]:=a[i-1,jj,j-1]+b[i,2]+b[i,1];
60                          end;
61                          4:begin
62                                 a[i,ii,j]:=a[i-1,ii,j]+b[i,2]+b[i,1];
63                                 for jj:=0 to 4 do if (j>=1) and (a[i,ii,j]1,jj,j-1]+b[i,2]+b[i,1]) then a[i,ii,j]:=a[i-1,jj,j-1]+b[i,2]+b[i,1];
64                          end;
65                     end;
66             end;
67     tot:=-maxlongint div 10;
68     for i:=0 to 4 do if totthen tot:=a[n,i,k];
69     writeln(tot);
70 end.