题解 - Vijos

9

猫粮寸断 LV 10 @ 2018-03-14 20:07:53

//其实思路并没有那么麻烦
//我们只需要把被咬的地方设成负无穷
//然后就可以很简单的跑一个最大子矩阵了
//总之就是强制最小嘛
#include<iostream>
using namespace std;
int map[510][510],sum[510][510];
int main()
{
        int n,m,i,j,k,lin=0,maxn=0;
        cin>>n>>m;
        for(i=1;i<=n;i++)
         for(j=1;j<=m;j++)
          {
           cin>>map[i][j];
           if(map[i][j]==0)
            map[i][j]=-1000000;
          }
        for(i=1;i<=n;i++)
         for(j=1;j<=m;j++)
          sum[i][j]=sum[i][j-1]+map[i][j];
        for(i=1;i<=m;i++)
         for(j=0;j<i;j++)
          {
                lin=0;
                for(k=1;k<=n;k++)
                {
                        lin+=sum[k][i]-sum[k][j];
                        maxn=max(maxn,lin);
                        if(lin<0)
                        {
                                lin=0;
                        }
                }
          }
        cout<<maxn<<endl;
        return 0;
}

1

眠 LV 4 @ 2018-06-09 11:40:17

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,a[1005][1005],f[1005],sum[1005][1005],maxx;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==0) a[i][j]=-10000000;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
sum[i][j]=sum[i-1][j]+a[i][j];
}
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
f[1]=sum[j][1]-sum[i-1][1];
maxx=max(f[1],maxx);
for(int k=2;k<=m;k++)
{
f[k]=max(f[k-1]+sum[j][k]-sum[i-1][k],sum[j][k]-sum[i-1][k]);
maxx=max(maxx,f[k]);
}
}
printf("%d\n",maxx);
return 0;
}

0

936255455 LV 8 @ 2015-07-20 17:48:38

与最大子矩阵和相似，不同的是要判断一下此矩阵是否成立，本菜就多设了一个C数组，计算矩阵中不为零数字的数量，如果小于矩阵的长乘宽，则不计入此答案
最大子矩阵和思路：http://blog.sina.com.cn/s/blog_575e6b9d010009fz.html
var n,m,i,j,k,l,ans,s,u:longint; a,b,c:array[1..300,1..300]of longint;
begin
readln(n,m);
fillchar(b,sizeof(b),0);
fillchar(c,sizeof(c),0);
for i:=1 to n do
for j:=1 to m do
begin
read(a[i,j]);
b[i,j]:=b[i,j-1]+a[i,j];
if a[i,j]>0 then c[i,j]:=1+c[i,j-1] else c[i,j]:=c[i,j-1];
end;
s:=0;
ans:=0;
l:=0;
u:=0;
for i:=1 to m do
for j:=i to m do
begin
u:=0;
l:=0;
s:=0;
for k:=1 to n do
begin
s:=s+b[k,j]-b[k,i-1];
u:=u+c[k,j]-c[k,i-1];
if u<(j-i+1)*(k-l) then begin u:=0;s:=0;l:=k; end;
if s<0 then begin u:=0; s:=0; l:=k; end;
if s>ans then ans:=s;
end;
end;
write(ans);
readln;
readln;
end.

0

niyinchen LV 9 @ 2015-03-06 20:18:53

uses math;

var f,a,s:array[0..300,0..300]of longint;max2:longint;

i,j,n,m:longint;b:Array[0..300,0..300]of boolean;

function pd1(x,y:longint):boolean;

var j:longint;

begin

for j:=1 to y do if a[x,j]=0 then exit(false);

exit(true);

end;

function pd2(y,x:longint):boolean;

var i:longint;

begin

for i:=1 to x do if a[i,y]=0 then exit(False);

exit(true);

end;

begin

readln(n,m);fillchar(b,sizeof(b),true);

for i:=1 to n do

begin

for j:=1 to m do

begin

read(a[i,j]);f[i,j]:=a[i,j];

s[i,j]:=s[i-1,j]+s[i,j-1]+a[i,j]-s[i-1,j-1];

if a[i,j]=0 then b[i,j]:=false

else b[i,j]:=b[i-1,j]and b[i,j-1];

end;

readln;

end;

for i:=1 to n do

for j:=1 to m do

if a[i,j]=0 then continue

else

begin

if (i=1)and(j=1) then continue;

if b[i-1,j-1] and pd1(i,j) and pd2(j,i) then

f[i,j]:=max(f[i,j],f[i-1,j-1]+s[i,j-1]+s[i-1,j]-2*s[i-1,j-1]+a[i,j]);

if pd1(i,j) then f[i,j]:=max(f[i,j],s[i,j]-s[i-1,j]);

if pd2(j,i) then f[i,j]:=max(f[i,j],s[i,j]-s[i,j-1]);

end;

max2:=0;

for i:=1 to n do

for j:=1 to m do

if f[i,j]>max2 then max2:=f[i,j];

writeln(max2);

end.

只对两个点，。不可能啊！！求教！！

0

juan1973 LV 10 @ 2013-11-02 07:59:27

测试数据 #0: Accepted, time = 656 ms, mem = 1176 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1180 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1180 KiB, score = 10
测试数据 #3: Accepted, time = 23 ms, mem = 1180 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1180 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 1176 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1180 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 1180 KiB, score = 10
测试数据 #8: Accepted, time = 265 ms, mem = 1176 KiB, score = 10
测试数据 #9: Accepted, time = 937 ms, mem = 1176 KiB, score = 10

n4！var
l,r,n,m,i,j,sum,ans,max:longint;
a:array[0..300,0..300] of longint;
begin
readln(n,m);
for i:=1 to n do
for j:=1 to m do
begin
read(a[i,j]);
if a[i,j]=0 then a[i,j]:=-1;
end;
for l:=1 to m do
for r:=l to m do
begin
sum:=0;
for i:=1 to n do
begin
max:=0;
for j:=l to r do
if a[i,j]>0 then max:=max+a[i,j]
else begin
max:=-1;
break;
end;
if max>0 then sum:=sum+max
else begin
if sum>ans then ans:=sum;
sum:=0;
end;
end;
if sum>ans then ans:=sum;
end;
writeln(ans);
end.

0

S.Y.F LV 10 @ 2013-10-27 09:23:56

写个o（N*m）的装逼！

0

ChinaLover LV 7 @ 2013-08-25 14:49:24

program mooncake;
var box:array[0..301,0..301] of longint;
n,m,i,j,l,x,y:longint;
value:array[0..301] of int64;
k,mm:int64;
procedure add;
var xx,yy:longint;
begin
for xx:=1 to m do
value[xx]:=value[xx]+box[y,xx];
end;
function max(a,b:int64):int64;
begin
if mm+value[i]>value[i] then max:=mm+value[i]
else max:=value[i];
end;
begin
readln(n,m);
for i:=1 to n do
for j:=1 to m do
begin
read(box[i,j]);
if box[i,j]=0 then box[i,j]:=-maxlongint;
end;
for x:=1 to n do
begin
for y:=x to n do
begin
add;
for i:=1 to m do
begin
mm:=max(mm+value[i],value[i]);
if mm>k then
k:=mm;
end;
mm:=0;
end;
fillchar(value,sizeof(value),0);
end;
writeln(k);
end.

0

ChinaLover LV 7 @ 2013-08-25 14:47:45

我用的一奇特的方法。。
搜索+DP+剪枝
虽然不是秒杀，但效率还挺高

0

ChinaLover LV 7 @ 2013-08-25 12:51:50

为什么不能公布数据呢

0

半度微凉 LV 10 @ 2012-11-05 12:40:44

测试数据 01：答案正确... (0ms, 4328KB)

├ 测试数据 02：答案正确... (0ms, 4328KB)

├ 测试数据 03：答案正确... (0ms, 4328KB)

├ 测试数据 04：答案正确... (0ms, 4328KB)

├ 测试数据 05：答案正确... (0ms, 4328KB)

├ 测试数据 06：答案正确... (0ms, 4328KB)

├ 测试数据 07：答案正确... (0ms, 4328KB)

├ 测试数据 08：答案正确... (0ms, 4328KB)

├ 测试数据 09：答案正确... (0ms, 4328KB)

├ 测试数据 10：答案正确... (0ms, 4328KB)

0

蓝凝星烁 LV 7 @ 2012-08-30 20:39:22

再买一盒或者放点老鼠药

0

936255455 LV 8 @ 2012-08-16 16:03:22

nm2次方

过了7个点

0

ChinaLover LV 7 @ 2012-07-27 10:42:37

好吧暴力穷举只拿了60

0

beckydzau LV 8 @ 2012-07-23 09:31:29

此题数据果然水...随便乱搞都90分~~-_-!!

解法一：O(nm^2);

如楼上所述~~...

解法二：O(nm);

以(i,j)向上到最近的‘0’为宽,dp求左边最大长,右边最大长,再合并

同理以向下最近的‘0’为宽,(以下省略16个字~)

我写得好恶心..120行~~~

解法三：O(nm);

跟解法二思路一样..不过用迭代求到左边和右边最大长

(本人甚水,如有谬误,请勿吐槽~————)

于是就是~~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

c16jjh LV 9 @ 2012-07-22 20:56:36

先将老鼠咬过的点"0" 变成 -maxint,方便下面处理

用f表示从(1,1)到(i,j)的月饼数目

用i,j (1=

0

zlfp2012 LV 8 @ 2012-07-20 17:20:13

program project1;

var a,sum:array[-1..305,-1..305] of longint;

n,m:longint;

procedure init;

var i,j:longint;

begin

read(n,m);

fillchar(sum,sizeof(sum),0);

for i:=1 to n do

for j:=1 to m do

begin

read(a);

if a=0 then a:=-999999;

sum:=sum+a;

end;

end;

procedure main;

var ans,head,tail,dsum,l,temp:longint;

begin

ans:=0;

for head:=1 to m do

for tail:=head to m do

begin

dsum:=0;

for l:=1 to n do

begin

temp:=sum[l,tail]-sum[l,head-1];

if tempans then ans:=dsum;

end;

end;

writeln(ans);

end;

begin

init;

main;

end.

0

林小雅 LV 10 @ 2010-04-03 16:47:37

编译通过...

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

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

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

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

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

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

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

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

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

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

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

OTL..两个都是119..

0

せ孤魂斩せ LV 8 @ 2009-11-10 18:34:27

囧开始忘记清零也能得20分...肯定有没有洞的数据

0

zhwhcfzl LV 7 @ 2009-11-02 22:17:55

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

树规？？

0

yue6 LV 6 @ 2009-10-29 21:46:38

O(n*m^2) 算法，转化成最优连续子序列求解，代码很短，25 行。等下用悬线法编个。提交了两次，因为，要用到[red] 64 位整型[/red]！

#include using namespace std;const long long minimum = -72057594037927936ll;long long matrix[1000][1000] = {{0ll}};inline long long delta(int i, int x, int y) { return (matrix[y][i] - matrix[x-1][i]); }int main() { int m, n, i, j, k; cin >> m >> n; for (i = 1; i matrix[i][j]; if (matrix[i][j] == 0ll) matrix[i][j] = minimum; matrix[i][j] += matrix[j]; } long long sum = 0ll, allsum = 0ll, d; for (i = 1; i

题解

118 条题解

月饼盒

信息

状态

开发

支持

题解

118 条题解

月饼盒

信息

状态

开发

支持

还没有账户？

登录