题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=12830&courseid=268
解题思路：本题应用到杨氏矩阵的特性。每一次选取上一行的最大值位置到这一行的第一个为正的位置，找到最大值，并一直这样到最后一行。
解题代码：
1 // File Name: I.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月20日 星期日 13时07分24秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 LL dp[1004][1004]; 28 int p[1005]; 29 int n , m ; 30 LL ans(int i , int j) 31 { 32 if(j > m ) 33 return -2LL*1e9; 34 return dp[n][m] - dp[i-1][m] - dp[n][j-1] + dp[i-1][j-1]; 35 } 36 int main(){ 37 int t; 38 scanf("%d",&t); 39 while(t--) 40 { 41 scanf("%d %d",&n,&m); 42 memset(dp,0,sizeof(dp)); 43 memset(p,0,sizeof(p)); 44 int temp ; 45 for(int i =1;i <= n;i ++) 46 { 47 int sum = 0 ; 48 for(int j =1;j <= m;j ++) 49 { 50 scanf("%d",&temp); 51 sum += temp; 52 dp[i][j] = dp[i-1][j] + sum; 53 if(temp < 0) 54 p[i]++; 55 } 56 } 57 LL a = max(ans(n,p[n]+1),1LL*temp); 58 temp = p[n]+1; 59 for(int i = n-1;i >= 1;i --) 60 { 61 for(int j = temp;j <= p[i]+1;j ++) 62 { 63 if(ans(i,j) >= a) 64 { 65 a = ans(i,j); 66 temp = j; 67 } 68 } 69 } 70 printf("%lld ",a); 71 } 72 73 return 0; 74 }