HDU 1081 二维DP裸题

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<iostream>
 4 using namespace std;
 5 
 6 #include<math.h>
 7 #include<algorithm>
 8 
 9 #define range 110
10 int a[range][range];
11 int b[range];
12 
13 int main()
14 {
15     int n;
16     while(scanf("%d",&n) != EOF)
17     {
18         for(int i=0; i<n; ++i)
19           for(int j=0; j<n; ++j)
20           scanf("%d", &a[i][j]);
21         
22         int maxSum = a[0][0];
23         
24         for(int i=0; i<n; ++i)
25         {
26             for(int k=0; k<n; ++k)
27               b[k]=0;
28              
29             for(int j=i; j<n; ++j)
30             {
31                 int temp = -0x3f3f3f3f;    
32                 for(int k=0; k<n; ++k)
33                 {
34                     b[k] += a[j][k];
35                     if(b[k] > temp) 
36                       temp = b[k];
37                 }
38                 
39                 if(temp <= 0)
40                 {
41                   if(temp > maxSum)  
42                   maxSum = temp;
43                 }
44                 
45                 else
46                 {  
47                     int tempMax = -0x3f3f3f3f;
48                     int cur=0;
49                     for(int k=0; k<n; ++k)
50                     {
51                         cur += b[k];
52                         if(cur > tempMax)  tempMax = cur;
53                         if(cur < 0)  cur=0;
54                     }
55                 
56                     if(tempMax > maxSum)  
57                     maxSum = tempMax;
58                 }        
59             }          
60         }
61         
62         printf("%d\n", maxSum);
63     }
64     
65     return 0;    
66 }