题解：P7074 [CSP-J2020] 方格取数

solution

方格取数，经典的动态规划问题，但有所不同。这里可以向上走，也要求不能重复取数。对于这个不同也很好处理，只需要多开一维记录当前格子从哪个方向转移，就可以避免类似刚从上面过来又往上走的问题。

所以，我们设

f_{i, j, k}

表示取数到

(i, j)

时的最大值，

k=0

表示从左转过来的，

k=1

表示从上转过来的，

k=2

表示从下转过来的。

绿色是当前格子，绿色根据

k

是由黄色转移到的，黄色是由红色转移得到，下面是对应的三种情况。

$k=0$ 时， $f_{i, j, 0} = \max(f_{i, j-1, 0}, f_{i, j-1, 1}, f_{i, j-1, 2})$ 。

CPP

for (int i=1; i<=n; i++)
      for (int j=1; j<=m; j++)
			f[i][j][0]=max({f[i][j-1][0], f[i][j-1][1], f[i][j-1][2]})+a[i][j];

$k=1$ 时， $f_{i, j, 1} = \max(f_{i, j-1, 0}, f_{i, j-1, 1})$ 。

CPP

for (int i=2; i<=n; i++)
      for (int j=1; j<=m; j++)
			f[i][j][1]=max(f[i-1][j][0], f[i-1][j][1])+a[i][j];

$k=2$ 时， $f_{i, j, 2} = \max(f_{i, j-1, 0}, f_{i, j-1, 2})$ 。

CPP

for (int i=n-1; i>=1; i--)
      for (int j=1; j<=m; j++)
			f[i][j][2]=max(f[i+1][j][0], f[i+1][j][2])+a[i][j];

因为有负数，所以实现的时候要注意初值设极小值。

code

CPP

#include <bits/stdc++.h>
using namespace std;
long long n, m, a[1005][1005], f[1005][1005][3];
int main () {
	cin >> n >> m;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
			cin >> a[i][j];
	memset(f, -0x3f, sizeof f);
	f[1][1][0]=f[1][1][1]=f[1][1][2]=a[1][1];
	for (int j=1; j<=m; j++) {
		for (int i=1; i<=n; i++)
			f[i][j][0]=max({f[i][j-1][0], f[i][j-1][1], f[i][j-1][2]})+a[i][j];
		for (int i=2; i<=n; i++)
			f[i][j][1]=max(f[i-1][j][0], f[i-1][j][1])+a[i][j];
		for (int i=n-1; i>=1; i--)
			f[i][j][2]=max(f[i+1][j][0], f[i+1][j][2])+a[i][j];
	}
	cout << max({f[n][m][0], f[n][m][1], f[n][m][2]});
	return 0;
}

题解：P7074 [CSP-J2020] 方格取数

文章操作

solution

code

相关推荐

评论

题解：P7074 [CSP-J2020] 方格取数