1084: [SCOI2005]最大子矩阵
1084: [SCOI2005]最大子矩阵
HansBug
发布于 2018-04-10 17:04:28
发布于 2018-04-10 17:04:28
1084: [SCOI2005]最大子矩阵
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1325 Solved: 670
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
Sample Output
9
HINT
Source
题解：看了半天不知道怎么办才好，直到发现M<=2（HansBug:呵呵你早说就俩列得了呗呵呵哒）假如这样的话那么直接根据此行俩数的不同情况讨论下不就得啦。。。情况繁一点
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]<a[i-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]<a[i-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]<a[i-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]<a[i-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]<a[i-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]<a[i-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]<a[i-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]<a[i-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 tot<a[n,i,k] then tot:=a[n,i,k];
69 writeln(tot);
70 end.本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-02-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录