2016年11月5日 星期六

TIOJ 1733 - 最大二維子矩陣

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

 跟1277幾乎一樣 但是這個一定要拿
不過不會差太多 先拿了 取完max之後 如果不好再刪掉就好

 

 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
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;

int i,j,k,rn,cn;
int a[52][52],ans,now,mx,rr[52][52];
bool take;

inline void t(int &x,int &y){
    now=0,mx=0,take=0;
    for(k=1;k<=cn;k++){
        now+=(rr[y][k]-rr[x-1][k]);
        take=1;
        ans=max(ans,now);
        if(now<0){
            now=0;
            take=0;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while(cin>>rn>>cn){
        memset(a,0,sizeof(a));
        memset(rr,0,sizeof(rr));
        ans=now=mx=0;
        for(i=1;i<=rn;i++){
            for(j=1;j<=cn;j++){
                cin>>a[i][j];
                for(k=1;k<=i;k++){
                    rr[i][j]+=a[k][j];
                }
            }
        }
        ans=a[1][1];
        for(i=1;i<=rn;i++){
            for(j=i;j<=rn;j++){
                t(i,j);
            }
        }
        cout<<ans<<endl;
    }
}
張貼者： 於

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)