首页 > ACM题库 > HDU-杭电 > HDU 2870-Largest Submatrix-动态规划-[解题报告]HOJ
2014
02-17

HDU 2870-Largest Submatrix-动态规划-[解题报告]HOJ

Largest Submatrix

问题描述 :

Now here is a matrix with letter ‘a’,'b’,'c’,'w’,'x’,'y’,'z’ and you can change ‘w’ to ‘a’ or ‘b’, change ‘x’ to ‘b’ or ‘c’, change ‘y’ to ‘a’ or ‘c’, and change ‘z’ to ‘a’, ‘b’ or ‘c’. After you changed it, what’s the largest submatrix with the same letters you can make?

输入:

The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 1000) on line. Then come the elements of a matrix in row-major order on m lines each with n letters. The input ends once EOF is met.

输出:

The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 1000) on line. Then come the elements of a matrix in row-major order on m lines each with n letters. The input ends once EOF is met.

样例输入:

2 4
abcw
wxyz

样例输出:

3

/*
分析:
    一道简单的dp。
    是hdu1505的小拓展、hdu1505又是hdu1506的小拓展- -,这个题
就是做三次hdu1505。昨晚敲完代码来不及提交就断网了囧~。凭水题
刷得多在hdu上面和一位主刷难题的学长题量平齐了,高兴倒没有,反
而因为想起那一届的学长而有点儿伤感了(他们去实习了已经)。。。
继续走吧,也没什么好伤感的,早晚咱也有洗洗手退出这条道儿的时
候,还是继续和还在这条道儿上粪斗的大伙儿一起粪斗吧,加油囧~。。。

                                                     2013-04-09
*/

#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int N=1005;

int n,m,ans;
char map[N][N],map_t[N][N];
int cnt[N][N],le[N],ri[N];

void solve(char cc,char a,char b,char c)
{
	int i,l,temp;

	for(i=1;i<=n;i++)
	for(l=1;l<=m;l++)
	{
		if(map[i][l]==a || map[i][l]==b || map[i][l]==c)
			map_t[i][l]=cc;
		else	map_t[i][l]=map[i][l];
	}
	
	memset(cnt[0],0,sizeof(cnt[0]));
	memset(map_t[0],0,sizeof(map_t[0]));
	for(i=1;i<=n;i++)
	{
		cnt[i][0]=cnt[i][m+1]=-1;
		for(l=1;l<=m;l++)
		{
			le[l]=ri[l]=l;
			if(map_t[i][l]!=cc)	cnt[i][l]=0;
			else	cnt[i][l]=cnt[i-1][l]+1;
		}
		for(l=2;l<=m;l++)
		{
			if(!cnt[i][l])	continue;
			while(cnt[i][le[l]-1]>=cnt[i][l])	le[l]=le[le[l]-1];
		}
		for(l=m-1;l>0;l--)
		{
			if(!cnt[i][l])	continue;
			while(cnt[i][ri[l]+1]>=cnt[i][l])	ri[l]=ri[ri[l]+1];
		}
		for(l=1;l<=m;l++)
		{
			if(!cnt[i][l])	continue;
			temp=cnt[i][l]*(ri[l]-le[l]+1);
			if(ans<temp)	ans=temp;
		}
	}
}
int main()
{
	int i;
	while(scanf("%d%d",&n,&m)!=-1)
	{
		for(i=1;i<=n;i++)	scanf("%s",map[i]+1);
		ans=0;
		solve('a','w','y','z');
		solve('b','w','x','z');
		solve('c','x','y','z');
		cout<<ans<<endl;
	}
	return 0;
}

解题参考:http://blog.csdn.net/ice_crazy/article/details/8780589


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法