1 条题解
-
0
【本题解由站长编写】
方格取数经典双路径 DP:两条路径同时从左上走到右下(同步走 k 步),f[k][i1][i2] 表示两条路径分别在第 i1、i2 行时的最大和;同一格只取一次(重合时只加一次值)。N≤10 状态数极小。
代码(C++17)
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<vector<int>> a(n, vector<int>(n, 0)); int x, y, v; while (cin >> x >> y >> v && (x || y || v)) a[x-1][y-1] = v; int S = 2 * n - 2; const long long NEG = -1e18; vector<vector<vector<long long>>> f(S + 1, vector<vector<long long>>(n, vector<long long>(n, NEG))); f[0][0][0] = a[0][0]; for (int k = 1; k <= S; k++) for (int i1 = 0; i1 < n; i1++) { int j1 = k - i1; if (j1 < 0 || j1 >= n) continue; for (int i2 = 0; i2 < n; i2++) { int j2 = k - i2; if (j2 < 0 || j2 >= n) continue; long long best = NEG; for (int d1 = 0; d1 < 2; d1++) for (int d2 = 0; d2 < 2; d2++) { int p1 = i1 - d1, p2 = i2 - d2; int q1 = j1 - (1 - d1), q2 = j2 - (1 - d2); if (p1 < 0 || p2 < 0 || q1 < 0 || q2 < 0) continue; if (f[k-1][p1][p2] == NEG) continue; best = max(best, f[k-1][p1][p2]); } if (best == NEG) continue; f[k][i1][i2] = best + a[i1][j1] + (i1 == i2 ? 0 : a[i2][j2]); } } cout << f[S][n-1][n-1] << endl; return 0; }
- 1
信息
- ID
- 4286
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者