icpc:problems:luogup7074
problems | |
---|---|
名称 | 方格取数 |
题目编号 | 2020 CSP-J T4 |
题目链接 | luogu.com.cn/… |
来源 | CCF |
算法分类 | 动态规划, 线性动态规划 |
难易程度 | 一般般 |
方格取数
想法
增加一个上下走的状态,限定每个状态的转移方向。
注意需要开long long int
代码实现
#include <algorithm> #include <cstdio> using namespace std; const int N = 1e3 + 10; int maps[N][N]; long long int f[N][N][2]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &maps[i][j]); for (int i = 0; i <= n + 1; i++) for (int j = 0; j <= m + 1; j++) f[i][j][1] = f[i][j][0] = -1e18; f[1][1][0] = f[1][1][1] = maps[1][1]; //[0] 从上往下, [1] 从下往上 for (int i = 1; i <= m; i++) { // 枚举每一列 for (int j = 1; j <= n && i != 1; j++) { f[j][i][0] = max(f[j][i - 1][0], f[j][i - 1][1]) + maps[j][i]; f[j][i][1] = max(f[j][i - 1][0], f[j][i - 1][1]) + maps[j][i]; } for (int j = n-1; j >= 1; j--) f[j][i][0] = max(f[j][i][0], f[j + 1][i][0] + maps[j][i]); for (int j = 2; j <= n; j++) f[j][i][1] = max(f[j][i][1], f[j - 1][i][1] + maps[j][i]); } printf("%lld", max(f[n][m][1], f[n][m][0])); return 0; }
/app/www/public/data/pages/icpc/problems/luogup7074.txt · 最后更改: 2024/03/26 06:23 由 温婕莺