1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <math.h> 5 #include <stdlib.h> 6 #include <map> 7 #include <set> 8 #include <vector> 9 #include <stack> 10 #include <queue> 11 #include <algorithm> 12 13 14 using namespace std; 15 16 17 #define mst(a,b) memset(a,b,sizeof(a)) 18 #define eps 10e-8 19 20 21 const int MAX_ = 110; 22 const int N = 100010; 23 const int INF = 0x7fffffff; 24 25 26 27 28 //int dir[3][2] = {{0,-1}, {1,0}, {0,1}}; 29 //bool vis[MAX_][MAX_]; 30 int mp[MAX_][MAX_]; 31 int num[MAX_][MAX_]; 32 int n, m, ans, cs; 33 34 35 36 37 void find(int x){ 38 for(int i = 1; i <= n; ++i){ 39 int tmp = num[i][x-1] + mp[i][x]; 40 if(num[i][x] < tmp)num[i][x] = tmp; 41 for(int j = i+1; j <= n; ++j){ 42 tmp += mp[j][x]; 43 if(tmp > num[j][x])num[j][x] = tmp; 44 } 45 } 46 for(int i = n; i > 0; --i){ 47 int tmp = num[i][x-1] + mp[i][x]; 48 if(num[i][x] < tmp)num[i][x] = tmp; 49 for(int j = i-1; j > 0; --j){ 50 tmp += mp[j][x]; 51 if(tmp > num[j][x])num[j][x] = tmp; 52 } 53 } 54 } 55 56 57 int main(){ 58 int T; 59 scanf("%d", &T); 60 for(int Ca = 1; Ca <= T; ++Ca){ 61 scanf("%Id%d", &n, &m); 62 for(int i = 1; i <= n; ++i){ 63 for(int j = 1; j <= m; ++j){ 64 scanf("%d", &mp[i][j]); 65 num[i][j] = -INF; 66 } 67 } 68 num[1][1] = mp[1][1]; 69 for(int i = 2; i <= n; ++i){ 70 num[i][1] = num[i-1][1] + mp[i][1]; 71 } 72 for(int i = 2; i <= m; ++i){ 73 find(i); 74 } 75 printf("Case #%d:\n%d\n",Ca, num[1][m]); 76 77 78 } 79 return 0; 80 }
原文:http://www.cnblogs.com/xiaoyeye/p/3762940.html