题解

118 条题解

  • 9
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2013-10-27 09:23:56

    写个o(N*m)的装逼!

  • 0
    @ 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
    @ 2013-08-25 14:47:45

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

  • 0
    @ 2013-08-25 12:51:50

    为什么不能公布数据呢

  • 0
    @ 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
    @ 2012-08-30 20:39:22

    再买一盒或者放点老鼠药

  • 0
    @ 2012-08-16 16:03:22

    nm2次方

    过了7个点

  • 0
    @ 2012-07-27 10:42:37

    好吧 暴力穷举只拿了60

  • 0
    @ 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
    @ 2012-07-22 20:56:36

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

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

    用i,j (1=

  • 0
    @ 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
    @ 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
    @ 2009-11-10 18:34:27

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

  • 0
    @ 2009-11-02 22:17:55

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

    树规??

  • 0
    @ 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

信息

ID
1255
难度
5
分类
动态规划 | 其他 点击显示
标签
(无)
递交数
1931
已通过
609
通过率
32%
被复制
2
上传者