收藏
关注
第1行：N，N为矩阵的大小。(2 <= N <= 500)
第2 - N + 1行：每行N个数，中间用空格隔开，对应格子中奖励的价值。（1 <= N[i] <= 10000)
输出能够获得的最大价值。
3
1 3 3
2 1 3
2 2 1
11
题意挺简单,就是用简单的动归就可以了.
1 #include <bits/stdc++.h> 2 #define N 505 3 #define bug cout<<"&&"<<endl 4 using namespace std; 5 int k[N][N]; 6 int main(){ 7 int n; 8 scanf("%d",&n); 9 for(int i=1;i<=n;i++){ 10 for(int j=1;j<=n;j++){ 11 scanf("%d",&k[i][j]); 12 } 13 } 14 //bug; 15 for(int i=n-1;i>=1;i--){ 16 k[n][i]+=k[n][i+1]; 17 k[i][n]+=k[i+1][n]; 18 } 19 for(int i=n-1;i>=1;i--){ 20 for(int j=n-1;j>=1;j--){ 21 k[i][j]+=max(k[i][j+1],k[i+1][j]); 22 } 23 } 24 printf("%d\n",k[1][1]); 25 return 0; 26 }
原文：http://www.cnblogs.com/zllwxm123/p/7368423.html