1057: [ZJOI2007]棋盘制作 - #include <Seter> - using namespace Orz;

1057: [ZJOI2007]棋盘制作

Seter posted @ 2011年12月13日 21:04 in BZOJ with tags ZJOI DP , 2613 阅读

http://www.zybbs.org/JudgeOnline/problem.php?id=1057

RunID User Problem Result Memory Time Language Code Length Submit Time
177478 Seter 1057 Accepted 8628 kb 512 ms C/Edit 787 B 2011-12-13 20:32:13

这个模板题老不做又忘了怎么做了……于是写了下,结果居然花了一个半小时……不断绕晕……我真是太水了……

以前做这类题的时候用的是自己的YY法(YY法的时间复杂度好像不对的?我现在连YY法都不会了)……现在专门学了王知昆神犇所说的“悬线法”……他说的非常清楚,ym一下!(不过这题是在格子里,要稍微改一下)

枚举每个点,记录向上的“悬线”长度(到第一个不能延伸处的长度),和这条悬线向左/向右最多能延伸到哪里。这些东西都可以用DP推出来。然后这就是一个极大子矩阵。而正方形必定也卡在某个极大子矩阵中。

时间复杂度是O(nm)的!

#include <stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
int n,m,l[2][2000],r[2][2000],h[2][2000],a1,a2;
_Bool v[2][2000],c;
char str[8010000],*p=str;
main(){
	int i=-1,j;
	for(scanf("%d%d",&n,&m),fread(p,1,8010000,stdin);++i!=n;c=!c){
		for(j=-1;++j!=m;l[c][j]=j&&v[c][j]!=v[c][j-1]?l[c][j-1]:j){
			while(*++p!=48&&*p!=49);v[c][j]=*p==49;
			h[c][j]=i&&v[c][j]!=v[!c][j]?h[!c][j]+1:1;
		}for(j=m;j--;r[c][j]=j!=m-1&&v[c][j]!=v[c][j+1]?r[c][j+1]:j)if(i&&v[c][j]!=v[!c][j])l[c][j]=max(l[c][j],l[!c][j]);
		for(j=m;j--;a1=max(a1,min(h[c][j],r[c][j]-l[c][j]+1)),a2=max(a2,h[c][j]*(r[c][j]-l[c][j]+1)))if(i&&v[c][j]!=v[!c][j])r[c][j]=min(r[c][j],r[!c][j]);
	}printf("%d\n%d\n",a1*a1,a2);
	return 0;
}

 

By Seter

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee