90pts,把所有的问题都找过了
查看原帖
90pts,把所有的问题都找过了
565707
mediocre_楼主2024/10/4 21:56

rt,正在备战CSP-J第二轮的我正在拼命训练

#include <bits/stdc++.h>
#define INF 100000000000000000
using namespace std;
const int N = 1005;
int n, m;
long long a[N][N], dp[N][N][3];
int dfs(int x, int y, int z) {
	if (x > n || y > m || x < 1) return -INF;
	if (dp[x][y][z] != -INF) return dp[x][y][z];
	if (x == n && y == m) return dp[x][y][z] = a[n][m];
	if (z == 1) return dp[x][y][z] = max(dfs(x + 1, y, 1), dfs(x, y + 1, 0)) + a[x][y];
	if (z == 2) return dp[x][y][z] = max(dfs(x - 1, y, 2), dfs(x, y + 1, 0)) + a[x][y];
	return dp[x][y][z] = max({dfs(x + 1, y, 1), dfs(x - 1, y, 2), dfs(x, y + 1, 0)}) + a[x][y];
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			scanf("%lld", &a[i][j]), dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = -INF;
	printf("%lld\n", dfs(1, 1, 0));
	/*
	for (int k = 0; k < 3; ++k, puts(""))
		for (int i = 1; i <= n; ++i, puts(""))
			for (int j = 1; j <= m; ++j)
				printf("%d ", dp[i][j][k]);
	*/
	return 0;
}

有两个点WA了

2024/10/4 21:56
加载中...