实质是把最大子段和扩展到二维。读题注意m,n。。。
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<algorithm> 5 #define CLR(a,b) memset((a),(b),sizeof((a))) 6 using namespace std; 7 const int N = 501; 8 int dp[N][N]; 9 int main(){ 10 int n, m, i, j, k, s, ans, x; 11 scanf("%d%d", &m, &n); 12 CLR(dp, 0); 13 for(i = 1; i <= n; ++i){ 14 for(j = 1; j <= m; ++j){ 15 scanf("%d", &x); 16 dp[i][j] = x + dp[i-1][j]; 17 } 18 } 19 ans = 0; 20 for(i = 1; i <= n; ++i){ 21 for(j = i; j <= n; ++j){ 22 s = 0; 23 for(k = 1; k <= m; ++k){ 24 x = dp[j][k] - dp[i-1][k]; 25 if(s > 0) 26 s += x; 27 else 28 s = x; 29 ans = max(ans, s); 30 } 31 } 32 } 33 printf("%d ", ans); 34 return 0; 35 }