首页 > 代码库 > 1084: [SCOI2005]最大子矩阵 - BZOJ

1084: [SCOI2005]最大子矩阵 - BZOJ

2024-07-06 22:39:48   231人阅读

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.
View Code

 


联系
我们