【BZOJ1084】【SCOI2005】最大子矩阵 笨动规

【BZOJ1084】【SCOI2005】最大子矩阵 傻动规

转载请注明出处：http://blog.csdn.net/vmurder/article/details/42913169

题解：

这数据范围，来乱搞吧少年。

我的乱搞：

m==1时做一遍，m==2时做一遍。

别讨论少情况就好，m==2时时间复杂度n^3。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 105
using namespace std;
int map[N][3],s[N][3],sum[N];
int f[N][N][12],g[N][12];
int n,m,p;
int main()
{
//	freopen("test.in","r",stdin);
	int i,j,k,t;
	scanf("%d%d%d",&n,&m,&p);
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&map[i][j]);
	if(m==1)
	{
		for(i=1;i<=n;i++)sum[i]=sum[i-1]+map[i][1];
		for(k=1;k<=p;k++)
		{
			for(i=1;i<=n;i++)
			{
				g[i][k]=max(g[i-1][k],g[i][k-1]);
				for(j=1;j<i;j++)
					g[i][k]=max(g[i][k],g[j][k-1]+sum[i]-sum[j]);
			}
		}
		printf("%d\n",g[n][p]);
	}
	else {
		for(i=1;i<=n;i++)
		{
			s[i][1]=s[i-1][1]+map[i][1];
			s[i][2]=s[i-1][2]+map[i][2];
			s[i][0]=s[i][1]+s[i][2];
		}
		for(k=0;k<=p;k++)
			for(i=0;i<=n;i++)
				for(j=0;j<=n;j++)
				{
					if(i)f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);
					if(j)f[i][j][k]=max(f[i][j][k],f[i][j-1][k]);
					if(k)f[i][j][k]=max(f[i][j][k],f[i][j][k-1]);
					if(i&&j)f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]);
					for(t=i+1;t<=n;t++)f[t][j][k+1]=max(f[t][j][k+1],f[i][j][k]+s[t][1]-s[i][1]);
					for(t=j+1;t<=n;t++)f[i][t][k+1]=max(f[i][t][k+1],f[i][j][k]+s[t][2]-s[j][2]);
						int temp=max(i,j);
					for(t=temp+1;t<=n;t++)f[t][t][k+1]=max(f[t][t][k+1],f[i][j][k]+s[t][0]-s[temp][0]);
				}
		printf("%d\n",f[n][n][p]);
	}
	return 0;
}