[ZJOI2007] 棋盘制作

悬线法。以每一个点向上达到的最长的长度作为悬线,左右扫,记录可以到达的最左边的长度以及最右边的长度,再以此更新答案即可。

更具体的, 表示从 往上最长的黑白相间的格子的高度;

表示从 往左最长的黑白相间的格子的长度;

表示从 往右最长的黑白相间的格子的长度;

在从上往下遍历每一行的时候,可以用上一行的 l,r 更新当前行的 l,r,并结合 up,可以算出当前矩形的长宽,然后更新答案即可。

#include<cstdio>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define ROF(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
const int N=2003;
int n,m,ans1,ans2;
int qp[N][N],up[N][N],l[N][N],r[N][N];
int main(){scanf("%d%d",&n,&m);
    FOR(i,1,n)FOR(j,1,m){scanf("%d",&qp[i][j]);
        l[i][j]=j==1?1:(qp[i][j]==qp[i][j-1]?1:l[i][j-1]+1);
    }
    FOR(i,1,n)ROF(j,m,1)r[i][j]=j==m?1:(qp[i][j]==qp[i][j+1]?1:r[i][j+1]+1);
    FOR(i,1,n)FOR(j,1,m){// 以 up[i][j] 为悬线
        if(i==1)up[i][j]=1;
        else {if(qp[i-1][j]==qp[i][j])up[i][j]=1;
            else {up[i][j]=up[i-1][j]+1;
                l[i][j]=min(l[i][j],l[i-1][j]);
                r[i][j]=min(r[i][j],r[i-1][j]);
            }
        }
        const int w=l[i][j]+r[i][j]-1,h=up[i][j];
        ans1=max(ans1,w*h),ans2=max(ans2,min(w,h)*min(w,h));
    }
    printf("%d\n%d",ans2,ans1);
    return 0;
}

  转载请注明: Sshwy's Blog [ZJOI2007] 棋盘制作

 上一篇
[ZJOI2005] 午餐 [ZJOI2005] 午餐
分析DP& 贪心 首先贪心地想到,让吃饭时间长的先排队(邻项微扰证明) 定义 表示前 i 个人,1 号窗口打饭总时间为 时的最早吃完饭的时间。 当第 个人在 1 号窗口时,吃完饭的时间为 $max
2018.11.18
下一篇 
[USACO08DEC]Trick or Treat on the Farm [USACO08DEC]Trick or Treat on the Farm
一颗基环树,则先处理环,再 DFS 处理其他结点即可 不知为何是蓝题 #include<cstdio> #include<queue> using namespace std; const int N=100005; int n
2018.11.17
  目录