题目意思：在一个n*m的矩阵中，不同的位置有不同重量的黄金，从矩阵的左上角开始，到右下角，只能向下或向右走，问最多能获得多少黄金？
思路：算出每个点到起点的最大值，找自己左面，上面，左上面的最大值加上自己即为最大值。
1 #include <iostream> //dp 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 int m[1100][1100]; //m数组放矩阵 7 int sum=0,r,c; 8 int dp(int x,int y) 9 { 10 return max(m[x-1][y],max(m[x][y-1],m[x-1][y-1])); 11 } 12 int main() 13 { 14 int n; 15 scanf("%d",&n); 16 for(int z=1;z<=n;z++) 17 { 18 scanf("%d%d",&r,&c); 19 memset(m,0,sizeof(m)); 20 for(int i=1;i<=r;i++) 21 for(int j=1;j<=c;j++) 22 scanf("%d",&m[i][j]); 23 for(int i=1;i<=r;i++) 24 for(int j=1;j<=c;j++) 25 m[i][j]+=dp(i,j); 26 printf("Scenario #%d: ",z); 27 printf("%d ",m[r][c]); 28 } 29 return 0; 30 } 31 32 #include <iostream> //深搜,在杭电上面提交时间超限。 33 #include <cstdio> 34 #include <cstring> 35 using namespace std; 36 int a[3][2]={{1,0},{0,1},{1,1}}; 37 int m[1100][1100]; 38 int sum=0,r,c; 39 void dfs(int x,int y,int s) 40 { 41 if(x==r-1&&y==c-1) 42 { 43 if(s>sum) 44 sum=s; 45 return; 46 } 47 int xx,yy; 48 for(int i=0;i<3;i++) 49 { 50 xx=x+a[i][0]; 51 yy=y+a[i][1]; 52 if(xx>=0&&xx<=r-1&&yy>=0&&yy<=c-1) 53 dfs(xx,yy,s+m[xx][yy]); 54 } 55 return; 56 } 57 int main() 58 { 59 int n; 60 scanf("%d",&n); 61 while(n--) 62 { 63 scanf("%d%d",&r,&c); 64 memset(m,0,sizeof(m)); 65 for(int i=0;i<r;i++) 66 for(int j=0;j<c;j++) 67 scanf("%d",&m[i][j]); 68 dfs(0,0,m[0][0]); 69 printf("%d ",sum); 70 } 71 return 0; 72 }