题目链接

分析和思路

题面很简单，就是求从左上到右下的最大代价（不允许重复）。但是唯一的一个限制使得这道看似简单的题成为了一个绿题，就是移动只有三个方向：右，上，下。
假如方向少了一个，只有向右和向下，那么这道题就成为了那个经典且简单的dp题，但是此时多了一个方向，使用原先的状态转移方程就失去了无后效性。

于是乎，我就不会用dp写了… 只会用dfs。dfs的思路很简单，傻傻向下搜，记录最大值就行了。如果不加入剪枝，记忆化等优化技巧，综合该题的数据范围。得到预估得分为30。

那么就还需要思考如何去写dp。
首先，我们思考，只能走右不能走左，意味着我们可以单独将每一列分开求解，而向右走其实是从某列运动到下一列，下一列再运动到下下一列……实质上是一个递推的过程。

然后对于每一列，我们会发现要么只能往上走，要么只能往下走。
于是可以考虑对于状态增加一维，记录来时的方向(dp[x][y][k])(k<3) 表示前x行，前y列，对于第k个方向来时取得的最大代价。
再考虑状态转移方程
我们先规定k=0时表示从左边来，k=1时表示从上面来，k=2时表示从下面来

dp[i][j][0]等于什么呢？
由于k=0，所以它的上一步只能从左边来，左边来的总代价可能有三种情况dp[i][j-1][0],dp[i][j-1][1],dp[i][j-1][2]，取最大值就好了，最后再加上它这个格子的代价
$$dp[i][j][0]=max(dp[i][j-1][0],dp[i][j-1][1],dp[i][j-1][2])+a[i][j]$$

再考虑dp[i][j][1]的状态转移方程
由于k=1,所以他的上一步只能从上面来，上面来的总代价就只有两种情况了dp[i-1][j][0],dp[i-1][j][1]。由于不能重复走，所以就不可能上面来的格子的更上一步从下面来，因此就不能将dp[i][j][2]考虑进去。所以它的状态转移方程为
$$dp[i][j][1]=max(dp[i-1][j][0],dp[i-1][j][1])+a[i][j]$$
同理可得k=2时的情况
$$dp[i][j][2]=max(dp[i+1][j][0],dp[i+1][j][2])+a[i][j]$$

想到这里，这题就完成大半了，接下来就是要将思路转换成代码。

实现与细节

  1. 十年OI一场空，不开long long见祖宗
    因此还是直接define int long long吧

  2. 初始化

    dp最难的细节就是初始化
    第一列直接初始化dp[i][j][1]

  3. 枚举顺序
    考虑递推的过程是按列的，所以外层循环枚举列
    再考虑到k=2时，前行被后行影响，所以要从后往前枚举

我关于这些细节踩过的坑

完整代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long // 开long long!!!
const int mx=1e3+10;
int a[mx][mx],m,n;
int dp[mx][mx][3];
signed main(){
	cin>>n>>m;
	for(int i=0;i<mx;i++){
		for(int j=0;j<mx;j++){
			for(int k=0;k<3;k++){
				dp[i][j][k]=-2e18;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) cin>>a[i][j];
	}
	dp[1][1][0]=dp[1][1][2]=dp[1][1][1]=a[1][1];
	for(int i=2;i<=n;i++){
		dp[i][1][1]=dp[i-1][1][1]+a[i][1];
	}
	for(int j=2;j<=m;j++){
		for(int i=1;i<=n;i++){
			dp[i][j][0]=max(max(dp[i][j-1][1],dp[i][j-1][2])
			,dp[i][j-1][0])+a[i][j];
		}
		for(int i=1;i<=n;i++){
			if(i>1)dp[i][j][1]=max(dp[i-1][j][0],dp[i-1][j][1])+a[i][j];
		}
		for(int i=n-1;i>=1;i--){
			dp[i][j][2]=max(dp[i+1][j][0],dp[i+1][j][2])+a[i][j];
		}
	}
	cout<<max(dp[n][m][0],dp[n][m][1]);
	return 0;
}

总结与反思

注重dp的特征，思考转移过程