AcWing 1015. 摘花生
原题链接
简单
作者:
摆神
,
2024-04-24 19:22:22
,
所有人可见
,
阅读 1
摘花生
(线性DP)
数字三角形
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int y,n,m;
int a[N][N];
int f[N][N];
int main(void)
{
cin >> y;
while(y -- > 0) {
cin >> n >> m;
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 ++) f[i][m] = a[i][m];
for(int i = 1;i <= m;i ++) f[n][i] = a[n][i];
for(int i = 1;i <= n+1;i ++) f[i][m+1] = 0;
for(int i = 1;i <= m+1;i ++) f[n+1][i] = 0;
for(int i = n;i >= 1;i --)
for(int j = m;j >= 1;j --){
f[i][j] = max( f[i+1][j] , f[i][j+1]) + a[i][j];
}
cout << f[1][1]<< endl;
}
return 0;
}