#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int p[1010][1010][2],n,m,bk[1010][1010],f[1010][1010][3],ma=1,a1,a2; int main(){ freopen("bigbrn.in","r",stdin); freopen("bigbrn.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&a1,&a2); bk[a1][a2]=1; } for(int i=1;i<=n;i++){ if(bk[i][1])p[i][1][0]=1; else p[i][1][0]=2; for(int j=2;j<=n;j++){ if(bk[i][j]==0)p[i][j][0]=p[i][j-1][0]; else p[i][j][0]=j+1; } } for(int i=1;i<=n;i++){ if(bk[i][n]==0)p[i][n][1]=n; else p[i][n][1]=n-1; for(int j=n-1;j>=1;j--){ if(bk[i][j]==0)p[i][j][1]=p[i][j+1][1]; else p[i][j][1]=j-1; } } for(int i=1;i<=n;i++){ if(bk[1][i]==0)f[1][i][0]=1,f[1][i][1]=p[1][i][0],f[1][i][2]=p[1][i][1]; else f[1][i][0]=2,f[1][i][1]=1,f[1][i][2]=n; } for(int i=2;i<=n;i++){ for(int j=1;j<=n;j++){ if(bk[i][j]==0){ f[i][j][0]=f[i-1][j][0]; f[i][j][1]=max(p[i][j][0],f[i-1][j][1]); f[i][j][2]=min(p[i][j][1],f[i-1][j][2]); } else{ f[i][j][0]=i+1; f[i][j][1]=1; f[i][j][2]=n; } if(bk[i][j]==0)ma=max(ma,min(i-f[i][j][0]+1,f[i][j][2]-f[i][j][1]+1)); } } printf("%d",ma); return 0; }

百题斩~~~~~~~~~~~

实在不太懂悬线法。。。
索性用动规写了。。。

悬线~

动归+滚动

和“家的范围”n^2算法一样一样滴

第一次广搜On3，以为不会超时，还是DP吧。