AcWing 1015. 摘花生
原题链接
简单
作者:
Jacky.C
,
2021-01-12 20:30:28
,
所有人可见
,
阅读 2
C++ 代码
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int dp(vector<vector<int>> map)
{
int h = map.size(), w = map[0].size();
vector<vector<int>> f(h, vector<int>(w,0));
f[0][0] = map[0][0];
for(int i = 1; i<h; i++){
f[i].resize(w);
f[i][0] = f[i-1][0] + map[i][0];
}
for(int i = 1; i<w; i++){
f[0][i] = f[0][i-1] + map[0][i];
}
for(int i = 1; i<h; i++){
for(int j = 1; j<w; j++){
f[i][j] = max(f[i-1][j], f[i][j-1]) + map[i][j];
}
}
return f[h-1][w-1];
}
int main()
{
int T, r, c;
vector<vector<int>> map;
cin>>T;
while(T--){
cin>>r>>c;
map.resize(r);
for(int i = 0; i<r; i++){
map[i].resize(c);
for(int j = 0; j<c; j++){
cin>>map[i][j];
}
}
cout<<dp(map)<<endl;
}
return 0;
}