枚举上下界，把里面的矩阵的数字纵向相加变成一维。

然后求最大子序列(O(n)算法，NOIP09年提高组程序完善第一题有程序)

复杂度是O(m*n^2)

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

sunny是怎么回事。。。为啥那么慢？这几天VJ都慢的要命……

还有，彩字怎么敲出来的？

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我悲剧的没有理解好极大化矩阵= =

热烈庆祝 AC第100题！！！！！！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

悬线法真是好东西~O(n*m)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

var

a1,a2,a3,a4,n,m,mm,add,max:longint;

x,sum:array[0..400,0..400] of longint;

f:array[0..400] of longint;

ok:boolean;

procedure prepare;

begin

readln(n,m);

for a1:=1 to n do

begin

for a2:=1 to m do read(x[a1,a2]);

readln;

end;

for a1:=1 to n do

for a2:=1 to m do

sum[a1,a2]:=sum[a1-1,a2]+x[a1,a2];

end;

begin

prepare;

for a1:=n downto 1 do

for a2:=a1-1 downto 0 do

begin

for a3:=1 to m do f[a3]:=sum[a1,a3]-sum[a2,a3];

mm:=0;

add:=0;

for a3:=1 to m do

begin

ok:=true;

for a4:=a2+1 to a1 do

if x[a4,a3]=0 then

begin

ok:=false;

break;

end;

if ok then

begin

add:=add+f[a3];

if add>mm then mm:=add;

end

else add:=0;

end;

if mm>max then max:=mm;

end;

writeln(max);

end.

不晓得有没有优化 n^4 汗

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

???

飘过……

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

原题Candy的数据范围是n,m

终于过了，不会优化搞了个O(n*n*m*m)的 也过了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一开始没判断sum

居然要用到int64

觉得用最大子矩阵不会超时。。。

这道题目从初二做到高一。。。。。。（3年！就算物是那人也非了）一直不会n^3的，今朝总算弱弱ac

var

i,j,max,n,m:longint;

h,l,r:array[0..301]of longint;

a,f:array[0..301,0..301]of longint;

begin

fillchar(f,sizeof(f),0); readln(n,m); max:=0;

for i:=1 to n do

for j:=1 to m do read(a);

for i:=1 to n do

for j:=1 to m do

f:=f+f-f+a;

for i:=1 to n do

begin

for j:=1 to m do if a=0 then h[j]:=0 else inc(h[j]);

for j:=1 to m do l[j]:=j; for j:=1 to m do r[j]:=j;

for j:=1 to m do if h[j]>0 then while (h[l[l[j]-1]]>=h[j])and(h[l[j]-1]>=h[j]) do l[j]:=l[l[j]-1];

for j:=1 to m do if h[j]>0 then while (h[r[r[j]+1]]>=h[j])and(h[r[j]+1]>=h[j]) do r[j]:=r[r[j]+1];

for j:=1 to m do if (f[i,r[j]]-f[i,l[j]-1]-f[i-h[j],r[j]]+f[i-h[j],l[j]-1])>max then

max:=f[i,r[j]]-f[i,l[j]-1]-f[i-h[j],r[j]]+f[i-h[j],l[j]-1];

end;

writeln(max);

end.

var

i,j,max,n,m:longint;

h,l,r:array[0..301]of longint;

a,f:array[0..301,0..301]of longint;

begin

fillchar(f,sizeof(f),0); readln(n,m); max:=0;

for i:=1 to n do

for j:=1 to m do

read(a);

for i:=1 to n do

for j:=1 to m do

f:=f+f-f+a;

for i:=1 to n do

begin

for j:=1 to m do

if a=0 then

h[j]:=0

else inc(h[j]);

for j:=1 to m do

l[j]:=j;

for j:=1 to m do

r[j]:=j;

for j:=1 to m do

if h[j]>0 then

while (h[l[l[j]-1]]>=h[j])and(h[l[j]-1]>=h[j]) do

l[j]:=l[l[j]-1];

for j:=1 to m do

if h[j]>0 then

while (h[r[r[j]+1]]>=h[j])and(h[r[j]+1]>=h[j]) do

r[j]:=r[r[j]+1];

for j:=1 to m do

if (f[i,r[j]]-f[i,l[j]-1]-f[i-h[j],r[j]]+f[i-h[j],l[j]-1])>max then

max:=f[i,r[j]]-f[i,l[j]-1]-f[i-h[j],r[j]]+f[i-h[j],l[j]-1];

end;

writeln(max);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

int main()

{

long n,m,i,j,k,l,ans,max;

long f[1050],a[550][550];

scanf("%d%d",&n,&m);

for(i=1;i

呃,我秒杀了,又是一个20行的程序.

题解:

var

a:array[1..1000,1..1000]of longint;

b:array[1..1000]of longint;

i,j,m,n,i1,i2:longint;

ans,max:int64;

begin

readln(m,n);

for i:=1 to m do

begin

for j:=1 to n do

begin

read(a);

if a=0 then a:=-500000;

end;

readln;

end;

for i2:=1 to n do

begin

fillchar(b,sizeof(b),0);

for i:=i2 to n do

begin

for j:=1 to m do

b[j]:=b[j]+a[j,i];

ans:=0;

for i1:=1 to m do

begin

inc(ans,b[i1]);

if ans>max then max:=ans;

if ans

编译通过...

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

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

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

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

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

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

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

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

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

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

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

Unaccepted 有效得分：80 有效耗时：0ms

O(n*n*m)还超时?

极大化

或者

转换成最大子矩阵问题（即被啃过的地方赋值成 -无限大）求解

只学会了O(n*m^2)……

！！不能用-maxlongint（溢出这种事情）