【BZOJ1084】最大子矩阵（动态规划）

题面

题目描述

这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。

输入输出格式

输入格式：

第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。

输出格式：

只有一行为k个子矩阵分值之和最大为多少。

输入输出样例

输入样例#1

3 2 2

1 -3

2 3

-2 3

输出样例#1

9

题解

还是我太菜

想了半天，发现连数据范围都没有看

\(m≤2\)

。。。

是我太菜，什么都看不见

既然\(m≤2\)，那么分情况直接搞就行了

第一种 \(m=1\)

很显然吧。。

设\(f[i][j]\)表示当前搞到第\(i\)行，已经选了\(j\)个子矩阵的最大值

暴力枚举一下上一个开始的位置

然后前缀和转移即可

第二种 \(m=2\)

设\(f[i][j][k]\)表示当前第一列的搞到\(i\)，第二列的搞到\(j\)，一共选了\(k\)个子矩阵的最大值

首先上下两列分开搞，类似\(m=1\)的转移，

然后当\(i=j\)时，显然可以两列一起转移

所以也类似于\(m=1\)的转移，

求和的时候搞两列的就行了

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

int n,m,g[200][5];

int K,f[101][101][15],s[5][200];

int ff[101][15];

int main()

{

	n=read();m=read();K=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			g[i][j]=read();

	for(int j=1;j<=m;++j)

		for(int i=1;i<=n;++i)

			s[j][i]=s[j][i-1]+g[i][j];

	if(m==1)

	{

		memset(ff,-63,sizeof(ff));

		ff[0][0]=0;

		for(int i=1;i<=n;++i)

		{

			ff[i][0]=0;

			for(int k=1;k<=K;++k)

			{

				ff[i][k]=ff[i-1][k];//不选

				for(int j=0;j<i;++j)

					ff[i][k]=max(ff[i][k],ff[j][k-1]+s[1][i]-s[1][j]);

			}

		}

		printf("%d\n",ff[n][K]);

	}

	else

	{

		memset(f,-63,sizeof(f));

		for(int i=0;i<=n;++i)

			for(int j=0;j<=n;++j)

				f[i][j][0]=0;

		for(int i=1;i<=n;++i)

			for(int j=1;j<=n;++j)

			{

				for(int k=1;k<=K;++k)

				{

					f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);

					f[i][j][k]=max(f[i][j][k],f[i][j-1][k]);

					for(int l=0;l<i;++l)

						f[i][j][k]=max(f[i][j][k],f[l][j][k-1]+s[1][i]-s[1][l]);

					for(int l=0;l<j;++l)

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

					if(i==j)

						for(int l=0;l<i;++l)

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

				}

			}

		printf("%d\n",f[n][n][K]);

	}

	return 0;

}