AcWing 1015. 摘花生
原题链接
简单
作者:
我是java同学
,
2023-01-11 12:44:42
,
所有人可见
,
阅读 132
集合
:所有从起点走到i
,j
这个点所有合法路线的集合
状态计算
:
关注最后一步
- 最后一步由两种方案,
所有最后一步是从上往下走的集合
,所有最后一步是从左往右走的集合
- 从(1,1)走到(i - 1, j),走最后一步(i, j);
- 分别求最大值,再加上相同的部分
对称思想
: i - 1
和j - 1
从上往下走
:f(i - 1, j) + w(i, j)
;
从左往右走
:f(i, j - 1) + w(i, j)
;
坐标
,边界
- 从实际问题出发考虑
- 涉及到
i - 1
, j - 1
之类的,下标都从1开始,不用处理边界,不用多加判断
- 默认左右两边
路径
可以画成图的形式,求的时候需要按拓扑序来算
- 只需要把i和j按从小到大循环就能保证是按照拓扑序来算的
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int w[N][N];
int f[N][N];
int main()
{
int T;
scanf("%d", &T);
while (T --)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
scanf("%d", &w[i][j]);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
f[i][j] = max(f[i - 1][j] + w[i][j], f[i][j - 1] + w[i][j]);
printf("%d\n", f[n][m]);
}
return 0;
}