4 6 11 0 7 5 13 9 78 4 81 6 22 4 1 40 9 34 16 10 11 22 0 33 39 6
242
解题:先求每一行的最大值,然后把这些最大值再求一次最大值。这道题目还是有点意思啦。慢慢想想还是可以解出来的。想再快点的话可以再开个数组,把后面那个循环里面的内容放到读入循环里面去。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <climits> 5 using namespace std; 6 int d[510][510],dp[510][2]; 7 int mx[510]; 8 int main() { 9 int r,c,i,j,temp,ans; 10 while(~scanf("%d %d",&r,&c)) { 11 for(i = 1; i <= r; i++) { 12 memset(dp,0,sizeof(dp)); 13 mx[i] = INT_MIN; 14 for(j = 1; j <= c; j++) { 15 scanf("%d",d[i]+j); 16 dp[j][0] = max(dp[j-1][0],dp[j-1][1]); 17 dp[j][1] = dp[j-1][0] + d[i][j]; 18 temp = max(dp[j][0],dp[j][1]); 19 mx[i] = max(temp,mx[i]); 20 } 21 } 22 memset(dp,0,sizeof(dp)); 23 ans = INT_MIN; 24 for(i = 1; i <= r; i++) { 25 dp[i][0] = max(dp[i-1][0],dp[i-1][1]); 26 dp[i][1] = dp[i-1][0] + mx[i]; 27 temp = max(dp[i][0],dp[i][1]); 28 if(temp > ans) ans = temp; 29 } 30 printf("%d\n",ans); 31 } 32 return 0; 33 }
原文:http://www.cnblogs.com/crackpotisback/p/3848000.html