首页 > 代码库 > 1084: [SCOI2005]最大子矩阵 - BZOJ
1084: [SCOI2005]最大子矩阵 - BZOJ
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
因为m≤2,所以就成了sbDP题,分情况DP即可
1 var 2 f1:array[0..100,0..10]of longint; 3 s1:array[0..100]of longint; 4 f2:array[0..100,0..100,0..10]of longint; 5 s2:array[0..100,1..2]of longint; 6 n,m,k:longint; 7 8 procedure up(var x:longint;y:longint); 9 begin 10 if x<y then x:=y; 11 end; 12 13 procedure work1; 14 var 15 i,j,l:longint; 16 begin 17 fillchar(f1,sizeof(f1),200); 18 for i:=1 to n do 19 begin 20 read(s1[i]); 21 inc(s1[i],s1[i-1]); 22 end; 23 for i:=0 to n do 24 f1[i,0]:=0; 25 for l:=1 to k do 26 for i:=1 to n do 27 begin 28 up(f1[i,l],f1[i-1,l]); 29 for j:=1 to i do 30 up(f1[i,l],f1[j-1,l-1]+s1[i]-s1[j-1]); 31 end; 32 writeln(f1[n,k]); 33 end; 34 35 procedure work2; 36 var 37 i,j,l,r:longint; 38 begin 39 for i:=1 to n do 40 for j:=1 to m do 41 begin 42 read(s2[i,j]); 43 inc(s2[i,j],s2[i-1,j]); 44 end; 45 fillchar(f2,sizeof(f2),200); 46 for i:=0 to n do 47 for j:=0 to n do 48 f2[i,j,0]:=0; 49 for l:=1 to k do 50 for i:=1 to n do 51 for j:=1 to n do 52 begin 53 up(f2[i,j,l],f2[i-1,j,l]); 54 up(f2[i,j,l],f2[i,j-1,l]); 55 for r:=1 to i do 56 up(f2[i,j,l],f2[r-1,j,l-1]+s2[i,1]-s2[r-1,1]); 57 for r:=1 to j do 58 up(f2[i,j,l],f2[i,r-1,l-1]+s2[j,2]-s2[r-1,2]); 59 if i=j then 60 for r:=1 to i do 61 up(f2[i,j,l],f2[r-1,r-1,l-1]+s2[j,2]-s2[r-1,2]+s2[i,1]-s2[r-1,1]); 62 end; 63 writeln(f2[n,n,k]); 64 end; 65 66 begin 67 read(n,m,k); 68 if m=1 then work1 69 else work2; 70 end.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。