题解 - Vijos

0

#include<bits/stdc++.h>
#define int long long
const int N=2001;
int n,m,l[N][N],r[N][N],ans,a[N][N],h[N][N],u,x,y,ans1;
char op;
inline int max(int x,int y)
{
    return x>y?x:y;
}
inline int min(int x,int y)
{
    return x<y?x:y;
}
inline void init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
}
signed main()
{
    init();
    std::cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            std::cin>>a[i][j],h[i][j]=1,l[i][j]=r[i][j]=j;
    for(int i=1;i<=n;i++)
        for(int j=2;j<=m;j++)
            if(a[i][j]+a[i][j-1]==1)
                l[i][j]=l[i][j-1];
    for(int i=1;i<=n;i++)
        for(int j=m-1;j>=1;j--)
            if(a[i][j]+a[i][j+1]==1)
                r[i][j]=r[i][j+1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(i>1&&a[i][j]+a[i-1][j]==1)
            {
                r[i][j]=min(r[i][j],r[i-1][j]);
                l[i][j]=max(l[i][j],l[i-1][j]);
                h[i][j]=h[i-1][j]+1;
            }
            ans=max(ans,min(r[i][j]-l[i][j]+1,h[i][j]));
            ans1=max(ans1,(r[i][j]-l[i][j]+1)*h[i][j]);
        }
    std::cout<<ans*ans<<"\n"<<ans1;
}

0

weapond LV 8 @ 8 年前

#include <iostream>
#include <string.h>
using namespace std;

const int maxn =2001;
int map[maxn][maxn]={0};
int n,m;
int dp[maxn][maxn]={0};
int max_squre(int target,int &ans){
    memset(dp,0,sizeof(dp));
    for(int i =1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(map[i][j]==target){
                dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
                ans = max(dp[i][j]*dp[i][j],ans);
            }
        }
    }
}


int max_rectangle(int target,int& ans){
    int dpl[2][maxn],dpr[2][maxn],templ[maxn],tempr[maxn];
    memset(dp,0,sizeof(dp));
    memset(dpl,0,sizeof(dpl));
    memset(dpr,0,sizeof(dpr));
    memset(templ,0,sizeof(templ));
    memset(tempr,0,sizeof(tempr));
    
    
    
    int mx =0;
    for(int i =1;i<=m;i++){
        dpl[0][i]=0,dpr[0][i]=m;
    }
    for(int i =1;i<=n;i++){
        int tmp =1;
        for(int j =1;j<=m;j++){
            if(map[i][j]!=target) tmp = j+1;
            else templ[j] = tmp;
        }
        tmp =m;
        for(int j=m;j>=1;j--){
            if(map[i][j]!=target) tmp = j-1;
            else tempr[j] = tmp;
        }
        for(int j =1;j<=m;j++){
            if(map[i][j]!=target){
                dp[i&1][j]=0,dpl[i&1][j] =1,dpr[i&1][j] = m;
                continue;
            }
            dp[i&1][j] = dp[(i&1)^1][j]+1;
            dpl[i&1][j] = max(dpl[(i&1)^1][j],templ[j]);
            dpr[i&1][j] = min(dpr[(i&1)^1][j],tempr[j]);
            mx = max((dpr[i&1][j]-dpl[i&1][j]+1/*加上自己*/)*dp[i&1][j],mx);
            
        } 
        
    }
    ans = max(ans,mx);
    
}
int main(){
    cin>>n>>m;
    
    //pre init
    for(int i =1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>map[i][j];
            if((i+j)%2==1){
                map[i][j] = 1-map[i][j];
            }
        }
    }
    
    
    //最大正方形 
    int ans=0;
    
    max_squre(1,ans);
    max_squre(0,ans);
    
    cout<<ans<<endl;
    
    ///最大子矩阵 
    max_rectangle(1,ans);
    max_rectangle(0,ans);
    cout<<ans<<endl;
    
    return 0;
}

测试数据 #0: Accepted, time = 15 ms, mem = 31952 KiB, score = 10
测试数据 #1: Accepted, time = 31 ms, mem = 31948 KiB, score = 10
测试数据 #2: Accepted, time = 31 ms, mem = 31948 KiB, score = 10
测试数据 #3: Accepted, time = 140 ms, mem = 31956 KiB, score = 10
测试数据 #4: Accepted, time = 125 ms, mem = 31952 KiB, score = 10
测试数据 #5: Accepted, time = 843 ms, mem = 31952 KiB, score = 10
测试数据 #6: Accepted, time = 1921 ms, mem = 31948 KiB, score = 10
测试数据 #7: Accepted, time = 1484 ms, mem = 31944 KiB, score = 10
测试数据 #8: Accepted, time = 3046 ms, mem = 31952 KiB, score = 10
测试数据 #9: Accepted, time = 3125 ms, mem = 31952 KiB, score = 10
Accepted, time = 10761 ms, mem = 31956 KiB, score = 100

weapond @ 8 年前

加上sync_with_stdio(false);
可以做到
测试数据 #0: Accepted, time = 15 ms, mem = 31940 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 31936 KiB, score = 10
测试数据 #2: Accepted, time = 31 ms, mem = 31936 KiB, score = 10
测试数据 #3: Accepted, time = 93 ms, mem = 31940 KiB, score = 10
测试数据 #4: Accepted, time = 93 ms, mem = 31940 KiB, score = 10
测试数据 #5: Accepted, time = 578 ms, mem = 31940 KiB, score = 10
测试数据 #6: Accepted, time = 1359 ms, mem = 31940 KiB, score = 10
测试数据 #7: Accepted, time = 1015 ms, mem = 31936 KiB, score = 10
测试数据 #8: Accepted, time = 2062 ms, mem = 31936 KiB, score = 10
测试数据 #9: Accepted, time = 2109 ms, mem = 31936 KiB, score = 10

0

王瑞程 LV 8 @ 8 年前

{
测试数据 #0: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 820 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 820 KiB, score = 10
测试数据 #3: Accepted, time = 78 ms, mem = 820 KiB, score = 10
测试数据 #4: Accepted, time = 46 ms, mem = 824 KiB, score = 10
测试数据 #5: Accepted, time = 734 ms, mem = 820 KiB, score = 10
测试数据 #6: Accepted, time = 2531 ms, mem = 820 KiB, score = 10
测试数据 #7: Accepted, time = 1281 ms, mem = 824 KiB, score = 10
测试数据 #8: Accepted, time = 5031 ms, mem = 820 KiB, score = 10
测试数据 #9: Accepted, time = 7046 ms, mem = 824 KiB, score = 10

用h[x]表示处理到当前行时第x列的连续01串长度，v[k]表示当前行起始于k的所有纵向连续01串的高度最小值（前提是从x开始横向的串是连续的），也就是矩阵的高。
p的含义需要解释一下。p是在当前行，处理到某个位置时，连续01串的起始位置，在p到当前位置的横向串都是连续的。p保证了上面提到的v[k]到横向的连续（for k:=p to j，k一定在p之后)。横纵都连续，那这一定是个完整的矩阵，长乘高得面积。
边界处理很特殊，所以第一行的读入、每一行第一个的读入、处理都单独拿出来了，以及最后一个也要专门处理一下。
这个算法有个重要的优化。不优化的话会超时0.015s......标出来了。
var
n,m,i,j,k,p,l,ans:longint;
map:array[1..2000,false..true]of shortint;
h,v:array[1..2000]of longint;
function min(a,b:longint):longint;
begin
IF A<B THEN EXIT(A) ELSE EXIT(B);
END;
function max(a,b:longint):longint;
begin
IF A>B THEN EXIT(A) ELSE EXIT(B);
END;
begin
readln(n,m);
ans:=0;
l:=1;
//初始化第一行
for i:=1 to m do
begin
read(map[i,true]);
h[i]:=1;
if (map[i,true]=map[i-1,true]) then//横向01串是否连续
p:=i;//不连续，将连续横向01串的起始位置设为j(实际保存为j-1)
for k:=p to i do//连续，更新矩阵高度，求最大面积
ans:=max(ans,(i-k+1));

end;

for i:=2 to n do
begin
p:=0;
read(map[1,(i and 1)=1]);
if (map[1,(i and 1)=1]=map[1,(i and 1)=0]) then
h[1]:=1//不连续，将高度设为1
else
inc(h[1]);//连续，高度加1
v[1]:=h[1];
ans:=max(ans,v[1]);
for j:=2 to m do
begin
read(map[j,(i and 1)=1]);
//第j列当前连续01串长度，
if (map[j,(i and 1)=1]=map[j,(i and 1)=0]) then
h[j]:=1//不连续，将高度设为1
else
inc(h[j]);//连续，高度加1
v[j]:=h[j];//v[x]记录下了横向起始于x位置，到当前处理位置中，所有纵向01串的最小高度（木桶原理），即01矩阵高度
if (map[j,(i and 1)=1]=map[j-1,(i and 1)=1]) then//横向01串是否连续
begin
//不连续，先赶紧更新之前的数据（因为之前有延迟，v[k]值不变就不计算)，将连续横向01串的起始位置设为j
for k:=p to j-1 do//对于j=m时的特殊对待
begin
ans:=max(ans,v[k]*(j-k));
l:=max(l,min(v[k],j-k));
end;
p:=j;
end;
for k:=p to j-1 do//连续，更新矩阵高度，求最大面积
if h[j]<v[k] then
//（优化：延迟计算）只有在发生v[k]变动的时候才计算和更新，因为在v[k]值不变的情况下，v[k]*(j-k)一定是随j递增的。此时计算的矩阵长度是k到j回退到前一个v[k]没有变动的的位置。但这样的延迟计算会导致当j等于m且串依然连续时，不会计算更新。所以对于j=m要特殊计算。
begin
ans:=max(ans,v[k]*(j-k));
l:=max(l,min(v[k],j-k));
v[k]:=h[j];
end;
end;
for k:=p to m do//对于j=m时的特殊对待
begin
ans:=max(ans,v[k]*(m-k+1));
l:=max(l,min(v[k],m-k+1));
end;
readln;
end;
writeln(l*l);
write(ans);
end.

0

S.Y.F LV 10 @ 11 年前

按照1255，极大化思想写就行了，但是还有一些不同点。
1255是如果是0就不能放，但是这里就是我和上面那行不同，我也可以单独成行，相当于也可以放。
这点需要注意。另外细心即可。
dxe

0

我是天才他哥 LV 10 @ 14 年前

直接悬线，第一二问全部解决

第一问都用盖房子方法...我感觉很诧异

0

邱国帅 LV 7 @ 15 年前

无情的秒杀……

程序有点错误，谁帮我看看

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案错误...

　├ Hint: 恩,900*1200　├ 标准行输出

　├ 错误行输出

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：153ms

var

n,m,i,j,ans,k,L,y,x,ans2:longint;

a:array[0..1,1..2000] of byte;

f:array[0..1,0..2000] of longint;

g,h:array[0..1,0..2000,1..2] of longint;

function min(x,y,z:longint):longint;

begin

min:=x;

if y

0

pheetleern LV 8 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 244ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 338ms

├ 测试数据 07：答案正确... 322ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 338ms

├ 测试数据 10：答案正确... 259ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1691ms

好丑……分数70－30－0－……－0－100……

最近老是写很SB的错误

0

jacklv LV 10 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 212ms

├ 测试数据 08：答案正确... 228ms

├ 测试数据 09：答案正确... 244ms

├ 测试数据 10：答案正确... 275ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：968ms

第一次接触这种思想，受益匪浅

0

darin LV 10 @ 15 年前

WS....偷懒没有“滚”起来。。没有一次a可惜啊。。哎。今天初赛rp全散光了。orz。。

0

chengrui LV 10 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 25ms

├ 测试数据 07：答案正确... 212ms

├ 测试数据 08：答案正确... 150ms

├ 测试数据 09：答案正确... 431ms

├ 测试数据 10：答案正确... 353ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1171ms

第363个AC!一次AC!

Orz 王知昆大牛的left,right,up方法!

Orz!

0

zxhzxh LV 10 @ 15 年前

交了好多遍，终于过了，我居然没赋初值。

0

M36_slugger LV 10 @ 15 年前

Accepted 有效得分：100 有效耗时：12206ms

有惊无险地过了 - -!

我真是傻x，第一问算错了害我改了两天………………

第二问不知道的自己想，不是特别难

0

fp_cxs LV 9 @ 15 年前

注意m和n 别搞混了

0

hxlong LV 10 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 41ms

├ 测试数据 07：答案正确... 244ms

├ 测试数据 08：答案正确... 181ms

├ 测试数据 09：答案正确... 447ms

├ 测试数据 10：答案正确... 447ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1360ms

正方形=DP盖房子（我盖房子枚举+优化的说）

矩形用模拟栈

100题纪念

0

FP_H LV 10 @ 15 年前

最大子矩阵变形

0

yzl609271536 LV 10 @ 15 年前

空间。。。

WA了一次

很WS的过了

0

notblack LV 10 @ 15 年前

盖房子+最大子矩形（悬线法） DP

O(NM)的时间

内存受不了，只好“滚”了。

真乃好题也~！！！

n,m搞反了，超级郁闷……

0

陈亮宇 LV 10 @ 15 年前

第一问： f=min(f,f);

f=min(f,f);

inc(f);

发现错了吗？我是一个下午之后才发现的

0

zhh1993 LV 10 @ 15 年前

j打成i折磨了我昨天一个下午，今天才发现.....

感谢题解，WC2003王知昆的论文真让人受益匪浅啊~~

0

myc427 LV 10 @ 15 年前

...好题阿～真是好题阿～～～～太经典了

还是看RP的题阿。。。

题解

52 条题解

棋盘制作

信息

状态

开发

支持

题解

52 条题解

棋盘制作

信息

状态

开发

支持

还没有账户？

登录