# 51 条题解

• @ 2016-11-17 16:12:28
``````#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

• @ 2016-11-17 16:18:58

加上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

• @ 2016-07-20 22:35:07

{
测试数据 #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
ans:=0;
l:=1;
//初始化第一行
for i:=1 to m do
begin
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;
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
//第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;
end;
writeln(l*l);
write(ans);
end.

• @ 2013-11-03 19:25:30

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

• @ 2010-07-14 09:53:12

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

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

• @ 2009-11-11 17:14:05

无情的秒杀……

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

编译通过...

├ 测试数据 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

• @ 2009-11-10 08:54:04

编译通过...

├ 测试数据 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的错误

• @ 2009-11-07 14:54:16

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

• @ 2009-10-17 23:08:35

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

• @ 2009-10-06 20:57:49

编译通过...

├ 测试数据 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!

• @ 2009-09-24 19:04:55

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

• @ 2009-09-19 19:58:02

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

有惊无险地过了 - -!

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

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

• @ 2009-09-16 20:18:37

注意m和n 别搞混了

• @ 2009-09-14 22:36:28

编译通过...

├ 测试数据 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题纪念

• @ 2009-09-14 13:44:26

最大子矩阵变形

• @ 2009-09-03 09:44:12

空间。。。

WA了一次

很WS的过了

• @ 2009-08-31 02:31:15

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

O(NM)的时间

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

真乃好题也~！！！

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

• @ 2009-08-26 18:53:42

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

f=min(f,f);

inc(f);

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

• @ 2009-08-17 13:23:11

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

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

• @ 2009-08-16 18:09:02

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

还是看RP的题阿。。。

• @ 2009-08-07 22:48:39

用A表示棋盘

对于正方形，可以类似于盖房子的模型

F=Min(F,F,F)+1

条件为 (Not(A Xor A))And(A Xor A)And(A Xor A)

即满足黑白相间的要求

对于矩形，可以利用极大化思想

F=H[J]*(R[J]-L[J]+1)

其中H[J]表示A向上最多可以延伸的高度，L[J],R[J]表示向左、右可以延伸的宽度

求L的代码如下

L[1]:=1;

For J:=2 to M do

Begin

L[J]:=J;

While(L[J]>1)And(H[J]

ID
1351

7

(无)

1029

233

23%

3