1027. 方格取数
题意
设有N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：
某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。
在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。
思路
dp 问题
最初想法 设 dp[i1][j1][i2][j2] 为 第一条路走到(i1,j1) 第二条路走到(i2,j2) 路径上数字和的最大值
可以想到 如果当前的横纵坐标已知 那么可以由横坐标推断出纵坐标 即可以减少一维
设dp[k][i1][i2] 表示 横纵坐标之和为k 且 其一条路行走到第i1 行 第二条路行走到i2 行 路径上数字和的最大值 三重循环即可 细节见代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 100100; int n; int g[20][20]; int dp[40][20][20]; void solve() { int a, b, c; while (cin >> a >> b >> c, a || b || c) { g[a][b] = c; } for (int k = 2; k <= 2 * n; ++k) { // 横纵坐标之和 for (int i1 = 1; i1 <= n; ++i1) { // 枚举第一条路线和第二条路线的横坐标 for (int i2 = 1; i2 <= n; ++i2) { int j1 = k - i1, j2 = k - i2; // 计算出第一条路线和第二条路线的纵坐标 int w = g[i1][j1]; if (i1 != i2)w += g[i2][j2]; // 总步数相同时 只有横坐标不相同，纵坐标才不相同 int &x = dp[k][i1][i2]; // 因为每一格都只能由它上面或者左边的方格转移过来 所以会有四种情况 // 第一个格子由上边转移过来 第二个格子由上边转移过来 x = max(x, dp[k - 1][i1 - 1][i2 - 1] + w); // 第一个格子由上边转移过来 第二个格子由左边转移过来 x = max(x, dp[k - 1][i1 - 1][i2] + w); // 第一个格子由左边转移过来 第二个格子由上边转移过来 x = max(x, dp[k - 1][i1][i2 - 1] + w); // 第一个格子由左边转移过来 第二个格子由左边转移过来 x = max(x, dp[k - 1][i1][i2] + w); } } } printf("%d\n", dp[n + n][n][n]); } int main() { //int t; cin >> t; //while (t--) solve(); return 0; }
