首页 > 代码库 > BZOJ1084: [SCOI2005]最大子矩阵

BZOJ1084: [SCOI2005]最大子矩阵

2024-07-17 16:00:44   221人阅读

1084: [SCOI2005]最大子矩阵

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1129  Solved: 578
[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

Sample Output

9

HINT

 

Source

题解：

DP的难点：

1.状态的表示  用几维变量分别代表什么信息能完整的代表一个状态，这是最重要的

2.状态的转移 枚举这个状态可能转移到什么状态或者可能有什么状态转移来，这是比较容易的

如果状态的转移感到复杂，有可能是状态的表示太过简单

想不到好的方法，就把状态分的细一点

对于本题来说

f[i,j,k]表示左边一列取到i 个，右边取到j个，共取了 k 次

当然并不是全取了，或者说是左边决策到了 i，右边决策到了 j，该进行第k次决策

状态的转移就十分明显了

代码：

 1 uses math; 2 const maxn=100+10;maxk=15; 3 var g:array[0..maxn,0..maxk] of longint; 4     s:array[1..2,0..maxn] of longint; 5     f:array[0..maxn,0..maxn,0..maxk] of longint; 6     i,j,k,l,t,n,m,x:longint; 7 procedure init; 8  begin 9    readln(n,m,t);10    for i:=1 to n do11     begin12       for j:=1 to m do begin read(x);s[j,i]:=s[j,i-1]+x;end;13       readln;14     end;15  end;16 procedure work1;17  begin18   fillchar(g,sizeof(g),0);19   for k:=1 to t do20    for i:=k to n do21     begin22     g[i,k]:=g[i-1,k];23     for j:=k-1 to i-1 do24      g[i,k]:=max(g[i,k],g[j,k-1]+s[1,i]-s[1,j]);25     end;26   writeln(g[n,t]);27  end;28 procedure work2;29  begin30   fillchar(f,sizeof(f),0);31   for k:=1 to t do32    for i:=0 to n do33     for j:=0 to n do34      begin35        if (i=0) and (j=0) then continue;36        f[i,j,k]:=max(f[i-1,j,k],f[i,j-1,k]);37        for l:=0 to j-1 do38         f[i,j,k]:=max(f[i,j,k],f[i,l,k-1]+s[2,j]-s[2,l]);39        for l:=0 to i-1 do40         f[i,j,k]:=max(f[i,j,k],f[l,j,k-1]+s[1,i]-s[1,l]);41        if i=j then42         for l:=0 to i-1 do43          f[i,j,k]:=max(f[i,j,k],f[l,l,k-1]+s[1,i]-s[1,l]+s[2,j]-s[2,l]);44      end;45   writeln(f[n,n,t]);46  end;47 48 begin49   assign(input,‘input.txt‘);assign(output,‘output.txt‘);50   reset(input);rewrite(output);51   init;52   if m=1 then work1 else work2;53   close(input);close(output);54 end.
View Code

 


联系
我们