poj 1050(矩阵求和问题dp)

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 #include <cstdio>
 5 #include <string>
 6 #include <cstring>
 7 #include <vector>
 8 #include <queue>
 9 #include <stack>
10 #include <set>
11 #define INF 0x3f3f3f3f
12 #define INFL 0x3f3f3f3f3f3f3f3f
13 #define zero_(x,y) memset(x , y , sizeof(x))
14 #define zero(x) memset(x , 0 , sizeof(x))
15 #define MAX(x) memset(x , 0x3f ,sizeof(x))
16 using namespace std ;
17 #define N 505
18 typedef long long LL ;
19 LL dp[N],a[N][N],s[N][N];
20 int main(){
21     //freopen("in.txt","r",stdin);
22     int n;
23     scanf("%d",&n);
24     zero(dp);zero(a);zero(s);
25     for(int i=1;i<=n;i++){
26         for(int j=1;j<=n;j++){
27             scanf("%I64d",&a[i][j]);
28         }
29     }
30     for(int i=1;i<=n;i++){
31         for(int j=1;j<=n;j++){
32             s[j][i]=s[j-1][i]+a[j][i];
33            
34         }
35     }
36    
37     LL sum=0,b=0;
38     for(int i=0;i<=n;i++){
39         for(int j=i+1;j<=n;j++){
40                 b=0;
41             for(int k=1;k<=n;k++){
42                 
43                 if(b>0)
44                     b+=(s[j][k]-s[i][k]);
45                 else
46                     b=s[j][k]-s[i][k];
47                 if(b>sum)
48                     sum=b;
49                 
50             }
52         }
53     }
54     printf("%I64d\n",sum);
55     return 0;
56 }