1312 偷西瓜 题解

曹浩源

题目传送门
AC代码:

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<algorithm>
   
4. using namespace std;
   
5. int t;
   
6. int r,c;
   
7. int w[110][110];//各个格点上花生数
   
8. int f[110][110];//递推数组
   
9. int main(){
   
10.     scanf("%d",&t);
    
11.     while(t--){
    
12.         scanf("%d%d",&r,&c);
    
13.         for(int i=1;i<=r;++i)
    
14.             for(int j=1;j<=c;++j)
    
15.                 scanf("%d",&w[i][j]);
    
16.         //求从(1,1)走到(i,j)的所有路线中的花生总和最大值
    
17.         //可以分解为两个子问题
    
18.         //1.从左边走到(i,j)
    
19.         //2.从上边走到(i,j)
    
20.         //f[i][j]选两个子问题的最大值即可
    
21.         for(int i=1;i<=r;++i)
    
22.             for(int j=1;j<=c;++j)
    
23.                 f[i][j]=max(f[i][j-1],f[i-1][j])+w[i][j];
    
24.         printf("%d\n",f[r][c]);
    
25.     }
    
26.     return 0;
    
27. }

复制代码

tiger

下次别发代码，会有人不劳而获