思路很简单。。主要是细节。。郁闷死了。。。

大家都细心哈。。

1.当h=1时的边界处理。=。=

2.在做f:=max(f,f+k-j+1)

这个方程要额外开一个数组。

下面这个数据

4 4 1

1 0 0 1

1 0 0 1

0 0 0 0

0 0 0 0

。。。

语文不好。

---|---|---|---|---|---|---|---|---|-总结这题---|---|---|---|---|---|---|---|---|-

终于AC了。。

AC率降了一点。。。。。。。。

一个下午+半个晚上。。。。。。

激动死了。。。。

---|---|---|---|---|---|---|---|---|--AC的分割线---|---|---|---|---|---|---|---|--

彻底崩溃。

---|---|---|---|---|---|---|---|---|--崩溃的分割线---|---|---|---|---|---|---|---|-

崩溃了。。

---|---|---|---|---|---|---|---|---|--华丽的分割线---|---|---|---|---|---|---|---|-

..看上去很水的样子。

O(n*m*m*h)貌似要超时。。

慢慢优化^.^

我沙茶了，写了题解的方法~。

在自己机上过了

然后vj还是超时两~可恶的sunny。

等puppy再交

恩~这里有解题报告和我的代码~供参考（copy无意义）；

http://hi.baidu.com/think%5Fexist/blog/item/f6182d3951ceafe014cecb6f.html

___|\__|\__|\__|\__|\__|\__|\___|_

换台机AC了 第100个哈哈

注意！！！

状态如下大牛们说的

对每个下限的f，若它有值则更新ans，最终状态有点搞错

提交了14次!

经历了 0~40~20 之间不断的波折起伏

ac 降了 百分之三

多么令人激动的AC 啊！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

咋办

大家帮忙看下我的程序错在哪儿呢?!

有一个数据卡死了...

90.....

const

maxh=40;

maxn=120;

maxm=120;

var

ans:int64;

n,m,h:longint;

i,j,k:longint;

s:array[0..maxn,0..maxm] of longint;

data:array[1..maxn,1..maxm] of longint;

f,g:array[0..1,-maxh..maxh,-maxm..maxm,-maxm..maxm] of longint;

procedure print;

begin

writeln(ans);

close(input);

close(output);

end;

function max(x,y:longint):longint;

begin

if x>y then exit(x)

else exit(y);

end;

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

begin

if x>y then exit(y)

else exit(x);

end;

procedure work;

var

l,r,t,w:longint;

begin

w:=0;

for i:=1 to n do begin

w:=1-w;

for j:=1 to min(h,i) do begin

for l:=1 to m do

if data=0 then begin

if (f[1-w,j,l,l]0)or(i=1)

then f[w,j,l,r]:=g[1-w,j-1,l+1,r-1]+t+1;

if (f[1-w,j,l,r]>0)or(i=1)

then f[w,j,l,r]:=max(f[w,j,l,r],f[1-w,j,l,r]+t+1);

g[w,j,l,r]:=max(g[w,j,l+1,r],max(g[w,j,l,r-1],f[w,j,l,r]));

end else begin

f[w,j,l,r]:=-maxint;

g[w,j,l,r]:=max(g[w,j,l+1,r],max(g[w,j,l,r-1],f[w,j,l,r]));

end;

end;

end;

ans:=max(ans,g[w,h,1,m]);

end;

end;

procedure init;

begin

assign(input,'stage.in');

reset(input);

assign(output,'stage.out');

rewrite(output);

readln(n,m,h);

for i:=1 to n do

for j:=1 to m do

read(data);

for i:=1 to n do

for j:=1 to m do

s:=s+data;

end;

begin

init;

work;

print;

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

递推。注意数组要开的比[1..20,1..100,1..100] (h,l,r)大些，不然错最后2点

就是90分！！！！

请原谅我小小地BS下Lora Temper

好不容易等到Vijos Dragon了。。。

CE两次..

Prog1221.pas(2,10) Fatal: Can't find unit objpas used by math

Fatal: Compilation aborted

楼下所言极是。边界谨慎处理。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

f表示以第i行下标为l,r的边为舞台底边且层数最大的h-舞台的面积

g表示以第i行下标在l,r以内的边为舞台底边且层数最大的h-舞台的面积

因为上层矩形横坐标要在下层矩阵内部

所以dp f数组时就要用到g数组

要不然你枚举l,r时,还要枚举lr之间的值

就费时了

直接用g数组省时间

而且g数组通过

g=Max{Max{g,g},f}

...总是超时

优化了滚动数组，去掉了多余的判断条件就Accepted了...

终于过了，虽然时间很高

编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 9ms├ 测试数据 06：答案正确... 72ms├ 测试数据 07：答案正确... 88ms├ 测试数据 08：答案正确... 134ms├ 测试数据 09：答案正确... 791ms├ 测试数据 10：答案正确... 791ms-------------------------Accepted 有效得分：100 有效耗时：1885ms

请问这道题是什么算法？

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

调了好久

虽然慢..但总算..我的一个下午..

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

``有幸成为第3个通过的人

感谢汤牛教的··滚动数组··！

Orz汤牛。。我们的老大·汤牛

－－－－－－－－－－－－－－－－－－－－－－－－Orz教主_Iek

终于不是车了。。

妈呀……

天...