2016年10月20日 星期四

TIOJ 1733 - 最大二維子矩陣

http://tioj.infor.org/problems/1733

跟1277很像
不過因為不能不拿 所以最大值的預設值隨便給個-INF就好了

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;

int rn,cn;
int m[55][55];
int add[55][55];

int main(){
    while(cin>>rn>>cn){
        memset(m,0,sizeof(m));
        memset(add,0,sizeof(add));
        for(int i=1;i<=rn;i++){
            for(int j=1;j<=cn;j++){
                cin>>m[i][j];
                for(int k=1;k<=i;k++){
                    add[k][j]+=m[i][j];
                }
            }
        }
        int mx=-(1<<28);
        for(int i=1;i<=rn;i++){
            for(int j=i;j<=rn;j++){
                int cur=0,prv=0;;
                for(int k=1;k<=cn;k++){
                    cur+=(add[j][k]-add[i-1][k]);
                    mx=max(mx,cur);
                    if(cur<add[j][k]-add[i-1][k])cur=add[j][k]-add[i-1][k];
                    mx=max(mx,cur);
                }
            }
        }
        cout<<mx<<endl;
    }
}
張貼者： 於

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)