52 条题解
-
0
conti123 LV 7 @ 1 年前
-
08 年前@
测试数据 #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 -
08 年前@
{
测试数据 #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. -
011 年前@
按照1255,极大化思想写就行了,但是还有一些不同点。
1255是如果是0就不能放,但是这里就是我和上面那行不同,我也可以单独成行,相当于也可以放。
这点需要注意。另外细心即可。
dxe -
014 年前@
直接悬线,第一二问全部解决
第一问都用盖房子方法...我感觉很诧异
-
015 年前@
无情的秒杀……
程序有点错误,谁帮我看看
编译通过...
├ 测试数据 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 -
015 年前@
编译通过...
├ 测试数据 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的错误 -
015 年前@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 9ms
├ 测试数据 07:答案正确... 212ms
├ 测试数据 08:答案正确... 228ms
├ 测试数据 09:答案正确... 244ms
├ 测试数据 10:答案正确... 275ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:968ms
第一次接触这种思想,受益匪浅 -
015 年前@
WS....偷懒没有“滚”起来。。没有一次a可惜啊。。哎。今天初赛rp全散光了。orz。。
-
015 年前@
编译通过...
├ 测试数据 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! -
015 年前@
交了好多遍,终于过了,我居然没赋初值。
-
015 年前@
Accepted 有效得分:100 有效耗时:12206ms
有惊无险地过了 - -!
我真是傻x,第一问算错了害我改了两天………………第二问不知道的自己想,不是特别难
-
015 年前@
注意m和n 别搞混了
-
015 年前@
编译通过...
├ 测试数据 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题纪念 -
015 年前@
最大子矩阵变形
-
015 年前@
空间。。。
WA了一次
很WS的过了 -
015 年前@
盖房子+最大子矩形(悬线法) DP
O(NM)的时间
内存受不了,只好“滚”了。
真乃好题也~!!!
n,m搞反了,超级郁闷……
-
015 年前@
第一问: f=min(f,f);
f=min(f,f);
inc(f);发现错了吗? 我是一个下午之后才发现的
-
015 年前@
j打成i折磨了我昨天一个下午,今天才发现.....
感谢题解,WC2003王知昆的论文真让人受益匪浅啊~~
-
015 年前@
...好题阿~真是好题阿~~~~太经典了
还是看RP的题阿。。。