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

1057: [ZJOI2007]棋盘制作

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

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)的！

1057
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17	`#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",a1a1,a2);` `return` `0;` `}`

By Seter