55012 - [CSP-J2020]方格取数（number）

解题思路

从上下走不方便看，先翻转一下，就变成了可以向下向左向右走。

设f[i][j][0]表示现在在(i,j)，向左。f[i][j][1]表示向右，则答案为max(f[n][m][0],f[n][m][1])。 因为向下走和前面方向无关，所以： f[i][j][k]=max(f[i-1][j][k],f[i-1][j][k])+a[i][j]。当然，两个方向一定要分别转移，一正一倒。

参考代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long dp[1001][1001][2];
int a[1001][1001], n, m;
int main() {
	//freopen("number.in", "r", stdin);
 	//freopen("number.out", "w", stdout);
 	cin >> n >> m;
 	for (int i = 1; i <= n; i++) {
 		for (int j = 1; j <= m; j++) {
 			scanf("%d", &a[i][j]);
 		}
 	}
 	memset(dp, 0x80, sizeof(dp));
 	dp[1][1][0] = 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][1] = dp[i][j][0] = max(dp[i][j - 1][0], dp[i][j - 1][1]) + a[i][j];
 		}
 		for (int i = 2; i <= n; i++) {
 			dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][1] + a[i][j]);
 		}
 		for (int i = n - 1; i >= 1; i--) {
 			dp[i][j][0] = max(dp[i][j][0], dp[i + 1][j][0] + a[i][j]);
 		}
 	}
 	cout << max(dp[n][m][0], dp[n][m][1]) << endl;
 	return 0;
}