【解题报告】洛谷P7074 方格取数

题目链接

https://www.luogu.com.cn/problem/P7074

思路

这道题目就是从 (1,1)(1,1) 开始随便走，不走重复的，只能向上向右和向下走一个，走到 (n,m)(n,m) ，问可以取到的最大是多少

乍一眼看过去跟之前的方格取数很像，实际上不一样

因为这里可以从下面转移过来，怎么办呢？

我们设 f[i][j][0/1]f[i][j][0/1] 表示从 (1,1)→(i,j)(1,1) \rightarrow (i,j) 的最大值 ，其中 0,10,1 分别表示从上方走过来，从下方走过来

于是我们进行一个记忆化搜索，就可以过了

这里重要的点在于设置状态，因为这道题目主要与众不同的地方就在于可以从下方转移过来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define int long long
using namespace std;
const int maxn=1005;
const int INF=1e9;
int n,m;
int a[maxn][maxn];
int f[maxn][maxn][5];
bool vis[maxn];
int dfs(int i,int j,int from)
{
	if(i<1||j<1||i>n||j>m) return -INF;
	if(f[i][j][from]!=-INF) 
	return f[i][j][from];
	if(from==0)
	f[i][j][from]=max(dfs(i+1,j,0),max(dfs(i,j-1,0),dfs(i,j-1,1)))+a[i][j];
	else
	f[i][j][from]=max(dfs(i-1,j,1),max(dfs(i,j-1,0),dfs(i,j-1,1)))+a[i][j];
	return f[i][j][from];
}
signed main()
{
	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++)
	{
		for(int j=1;j<=m;j++)
		f[i][j][0]=f[i][j][1]=-INF;
	}
	f[1][1][0]=f[1][1][1]=a[1][1];
	cout<<dfs(n,m,1)<<'\n';
	return 0;
}