【bzoj1084】最大子矩阵

  • 本文为博主原创，未经许可不得转载

刚看到题的时候我傻眼了，这东西不是npc问题吗

然后看到数据范围m<=2，我*分类大讨论！

当m=1时，显然

$f[i][j]=f[i-1][j]$

$f[i][j]=f[k][k-1]+sum[i]-sum[k]$

当m=2是，状态要设成三维的

$f[i][j][k]=f[i-1][j][k],f[i][j-1][k]$

$f[i][j][k]=max(f[l][j][k-1]+sum[i][1]-sum[l][1],f[i][l][k-1]+sum[j][2]-sum[l][2])$

$f[i][j][k]=max(f[l][l][k-1],sum[i][1]+sum[j][2]-sum[l][1]-sum[l][2])　　(i==j)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
#define FILE "read"
#define INF (int)1e9
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
int n,m,T,sum[110][5];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
namespace solution1{
	int f[110][110];
	void solve(){
		for(int i=0;i<=n;++i)for(int j=1;j<=T;++j)f[i][j]=-INF;
		for(int i=1;i<=n;++i)for(int j=1;j<=T;++j){
			f[i][j]=f[i-1][j];
			for(int k=0;k<i;++k) 
				cmax(f[i][j],f[k][j-1]+sum[i][1]-sum[k][1]);
		}
		printf("%d\n",f[n][T]);
	}
}
namespace solution2{
	int f[110][110][110];
	void solve(){
		for(int i=0;i<=n;++i)for(int j=0;j<=n;++j)for(int k=1;k<=T;++k)f[i][j][k]=-INF;
		for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)for(int k=1;k<=T;++k){
			f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);
			for(int l=0;l<i;++l)  cmax(f[i][j][k],f[l][j][k-1]+sum[i][1]-sum[l][1]);
			for(int l=0;l<j;++l)  cmax(f[i][j][k],f[i][l][k-1]+sum[j][2]-sum[l][2]);
			if(i==j) for(int l=0;l<i;++l) cmax(f[i][j][k],f[l][l][k-1]+sum[i][1]+sum[j][2]-sum[l][1]-sum[l][2]);
		}
		printf("%d\n",f[n][n][T]);
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();  T=read();
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) sum[i][j]=sum[i-1][j]+read();
	if(m==1) {
		using namespace solution1;
		solve();
	}
	else{
		using namespace solution2;
		solve();
	}
	return 0;
}

本文标题:【bzoj1084】最大子矩阵

文章作者:chty

发布时间:2017年04月09日 - 20时25分

最后更新:2018年03月02日 - 17时32分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,