|
|
题目传送门
AC代码:
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- int t;
- int r,c;
- int w[110][110];//各个格点上花生数
- int f[110][110];//递推数组
- int main(){
- scanf("%d",&t);
- while(t--){
- scanf("%d%d",&r,&c);
- for(int i=1;i<=r;++i)
- for(int j=1;j<=c;++j)
- scanf("%d",&w[i][j]);
- //求从(1,1)走到(i,j)的所有路线中的花生总和最大值
- //可以分解为两个子问题
- //1.从左边走到(i,j)
- //2.从上边走到(i,j)
- //f[i][j]选两个子问题的最大值即可
- for(int i=1;i<=r;++i)
- for(int j=1;j<=c;++j)
- f[i][j]=max(f[i][j-1],f[i-1][j])+w[i][j];
- printf("%d\n",f[r][c]);
- }
- return 0;
- }
|
|
发表于 2022-12-7 19:46:19
置顶卡