今天考试,出了这题,只不过数据开大了,硬着头皮优化,好不容易到了O(nm),

竟一次全过……

o(n^2m^2)

AC好爽～～

随便怎么做应该都能过吧

难度1

简单的题目，将有洞的格子的值取为一个大负数，然后求一个最优子矩阵就OK了。

数据是没错的

我听了一楼的大牛，用EOF，超时N次

可能数据不知道什么时候改了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

O(nm)的算法谁可以讲下？

O(nm)

编译通过...

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

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

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

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

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

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

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

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

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

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

O(n*m)的算法

{f表示(1,1)到(i,j)糖果的个数

用l,r标号

l表示左边可到的点的坐标

r表示右边可到的点的坐标

从上至下不断更新两边可到的最大值

直到遇到hole

求出糖果数后更新最大值max，并开始重新扩展

}

楼下这位大牛

佩服

方法确实巧妙

O(mn^2)

nm不可能

不知道C，怎么求D？

不知道D，怎么求C？

P.S.对O(nm)的大牛致敬，并请你谈谈做法，别让我在难度为1的题上晕菜

yeah~~~O(nm)的 ~~

过咯~~

数据没错！

也不用二分

无聊题........好多道类似的了!

这个题的数据有问题，在读入的时候不要管他给的行数和列数，需要自己统计有多少行，多少列，他给的m,n的值根本就不对

。。。。。。

其实并不用那么复杂的。
维护一个单调递增的栈。
具体看代码。
c++
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m;
int ans;
int head,tail;
int a[1005][1005];
int sum[1005];
int l[1005];
int r[1005];
int q[1005];
int dp[1005][1005];
int read()
{
int x=0,f=1,ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-'){f=-1;}ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j]=read();
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]==0)
{
sum[j]=0;
}
else
{
sum[j]++;
}
}
sum[m+1]=0;
tail=0;
for(int j=1;j<=m+1;j++)
{
while(tail>=1&&sum[j]<sum[q[tail]])
{
ans=max(dp[i][j-1]-dp[i][q[tail-1]]-dp[i-sum[q[tail]]][j-1]+dp[i-sum[q[tail]]][q[tail-1]],ans);
tail--;
}
tail++;
q[tail]=j;
}
}
printf("%d",ans);
return 0;
}


var
  a,s,h,l,r:array[0..1001,0..1001]of longint;
    i,j,t,n,m,ans:longint;
function min(x,y:longint):longint;
begin
  if x<y then exit(x) else exit(y);
end;
function max(x,y:longint):longint;
begin
  if x>y then exit(x) else exit(y);
end;
begin
  fillchar(s,sizeof(s),0);
  readln(n,m);
    ans:=0;
    h[0,1]:=0;
    for i:=1 to n do
    begin
      for j:=1 to m do
        begin
          read(a[i,j]);
            s[i,j]:=a[i,j]+s[i-1,j]+s[i,j-1]-s[i-1,j-1];
          if a[i,j]<>0 then h[i,j]:=h[i-1,j]+1 else h[i,j]:=0;
        end;
      t:=0;
        for j:=1 to m do
          if h[i,j]=0 then begin l[i,j]:=0;t:=j; end
            else
              if h[i-1,j]=0 then l[i,j]:=j-t else l[i,j]:=min(j-t,l[i-1,j]);
        t:=m+1;
        for j:=m downto 1 do
          if h[i,j]=0 then t:=j
            else
              if h[i-1,j]=0 then r[i,j]:=t-j else r[i,j]:=min(t-j,r[i-1,j]);
        for j:=1 to m do
        begin
          t:=s[i,j+r[i,j]-1]-s[i,j-l[i,j]]-s[i-h[i,j],j+r[i,j]-1]+s[i-h[i,j],j-l[i,j]];
          ans:=max(ans,t);
        end;
        readln;
    end;
    write(ans);
end.