AcWing 1015. 摘花生
原题链接
简单
作者:
wyf
,
2021-01-28 23:01:47
,
所有人可见
,
阅读 260
线性dp:f[i][j]表示前i行前j列能取到的最大花生数。我们每次可以从左边过来也可以从上边下来,每次我们只需要找二者的最大值,再加上当前点的花生数即可,那么f[n][m]即为答案(如果我们下标从0开始会处理边界,若从1开始则不需要,故我们这里下标从1开始)
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int q[N][N];
int f[N][N];
int main(){
int T;
cin>>T;
while(T--){
int n,m;
cin>>n>>m;
memset(q,0,sizeof q);
memset(f,0,sizeof f);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>q[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=max(f[i-1][j],f[i][j-1])+q[i][j];
cout<<f[n][m]<<endl;
}
return 0;
}