AcWing 1015. 摘花生
原题链接
简单
作者:
嘗
,
2023-05-08 20:37:37
,
所有人可见
,
阅读 86
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int a[N][N];
int f[N][N];
/**
* 题解
* 首先是状态转移方程的解读:
* 状态表示: f[i][j]:表示人从起点(1, 1)到(i, j)最大采摘花生数量
* 因为题目之中说了每次只能向下或者是向右,所以对于所有的状态都只能从上面或者左面转移过来。
* 状态计算: f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];
*/
void solve()
{
cin >> n >> m;
memset(f, 0, sizeof f);
memset(a, 0, sizeof a);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
cin >> a[i][j];
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
f[i][j] = max(f[i][j - 1], f[i - 1][j]) + a[i][j];
cout << f[n][m] << endl;
}
int main()
{
int tt; cin >> tt;
while(tt --) solve();
return 0;
}