M_sea

洛谷1169 [ZJOI2007]棋盘制作
Luogu算法对于一个国际象棋棋盘:黑色格行列奇偶性相同,白色格不同白色格行列奇偶性相同,黑色格不同那么第一种情况...
扫描右侧二维码阅读全文
07
2018/02

洛谷1169 [ZJOI2007]棋盘制作

Luogu

算法

对于一个国际象棋棋盘:

  • 黑色格行列奇偶性相同,白色格不同
  • 白色格行列奇偶性相同,黑色格不同

那么第一种情况设0,第二种情况设1,然后求最大子矩形即可。

当然选择悬线法。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;
int n,m;
bool a[2010][2010];
inline void build1() { //第一次转换
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=m;j++) {
            if ((i&1)==(j&1)) a[i][j]=(a[i][j]==1);
            else a[i][j]=(a[i][j]==0);
        }
}
inline void build2() { //第二次转换
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=m;j++)
            a[i][j]=!a[i][j];
}
int s[2010],w[2010],top=0;
int f[2010][2010];
int ans1=-1,ans2=-1;
inline void DP() {
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) {
            if (a[i][j]) f[i][j]=f[i][j-1]+1;
            else f[i][j]=0;
        }
    for (re int j=1;j<=m;j++) {
        top=0;
        for (re int i=1;i<=n+1;i++) {
            int Min=i;
            while (top&&s[top]>=f[i][j]) {
                ans1=max(ans1,s[top]*(i-w[top]));
                ans2=max(ans2,min(s[top],i-w[top])*min(s[top],i-w[top]));
                Min=w[top]; top--;
            }
            top++; s[top]=f[i][j]; w[top]=Min;
        }
    }
}
mainint main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=m;j++)
            cin>>a[i][j];
    build1(); DP();
    build2(); DP();
    cout<<ans2<<endl<<ans1<<endl;
    return 0;
}
最后修改:2019 年 01 月 05 日 04 : 23 PM

发表评论