正题

题目链接:https://www.luogu.org/problemnew/show/P1169

---

题目大意

一个矩阵中求一个最大的子矩阵和子正方形使得它们其中都是01交错。

---

解题思路

$lef{t}_{i,j}$表示$(i,j)$往左扩展多远，$righ{t}_{i,j}$表示$(i,j)$往右扩展多远，$u{p}_{i,j}$表示$(i,j)$向上扩展多少个。

然后对于每个点作为最下边的点时答案为
$$le{n}_{i,j}=u{p}_{i,j}+max\{lef{t}_{k,j},righ{t}_{k,j}\}(j-k<u{p}_{i,j})$$
$$ans1=u{p}_{i,j}\ast le{n}_{i,j}$$
$$ans2=min\{u{p}_{i,j},le{n}_{i,j}{\}}^2$$

---

$code$

// luogu-judger-enable-o2 #include<cstdio> #include<algorithm> using namespace std; const int N=2100; int n,m,a[N][N],right[N][N],left[N][N],up[N][N],ans1,ans2; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);for(int i=1;i<=n;i++)for(int j=m;j>=1;j--){right[i][j]=(a[i][j]!=a[i][j+1]?right[i][j+1]:j);if(j==m) right[i][j]=m;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){left[i][j]=(a[i][j]!=a[i][j-1]?left[i][j-1]:j);if(j==1) left[i][j]=1;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){up[i][j]=1;if(i>1&&a[i][j]!=a[i-1][j]){left[i][j]=max(left[i][j],left[i-1][j]);right[i][j]=min(right[i][j],right[i-1][j]);up[i][j]=up[i-1][j]+1;}int l=right[i][j]-left[i][j]+1;int w=min(up[i][j],l); ans1=max(l*up[i][j],ans1);ans2=max(w*w,ans2);}printf("%d\n%d",ans2,ans1); }

总结

以上是生活随笔为你收集整理的P1169-[ZJOI2007]棋盘制作【贪心】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。