AcWing 1015. 摘花生
原题链接
简单
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define INF 0x3f3f3f3f
#define endl "\n"
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef long long LL;
const int N = 103;
int n,r,c;
int g[N][N],dp[N][N];
int dfs(int x,int y){
if(x < 1 || x > r || y < 1 || y > c) return 0;//越界返回0
if(dp[x][y] != -1) return dp[x][y];//当前位置已经遍历过或当前到达最后一点,直接返回
if(dp[x+1][y] == -1) dp[x+1][y] = dfs(x+1,y);
if(dp[x][y+1] == -1) dp[x][y+1] = dfs(x,y+1);
dp[x][y] = max(dp[x+1][y],dp[x][y+1]) + g[x][y];//当前最多摘到的花生为往右或下摘到花生的最大值+当前位置花生数
return dp[x][y];
}
void solve(){
cin >> r >> c;
memset(dp,-1,sizeof dp);
for(int i = 1;i <= r;++i) for(int j = 1;j <= c;++j) cin >> g[i][j];
dp[r][c] = g[r][c];//最后一点花生数量最大值就是本身
cout << dfs(1,1) << endl;
}
int main(){
#ifdef LOCAL
freopen(".w/ac.in","r",stdin);
freopen(".w/ac.out","w",stdout);
#endif
IOS;
int TT = 1;
cin >> TT;
while(TT--) solve();
return 0;
}