相关信息
原题:洛谷 P1006。
WA 代码
思路是之前 P1004 的 3 维 DP(见 P1004 题解区)小改了一下,不知道错在哪里。
代码:
#include <stdio.h>
#define MAX_N 50
int n, m, map[MAX_N][MAX_N]; /* 列数、行数、地图。
* 地图储存是 map[x][y],且坐标从 0 开始。
*/
int dp[MAX_N * 2][MAX_N][MAX_N]; /* DP 数组。
* f(k, x_1, x_2),k 是 纸条已走的步数(或说 到00原点的曼哈顿距离),
* x_1, x_2 是两张纸条的 X 坐标,k-x 可以得到相应 y 坐标。
* 两张纸条同时从左上角开始传。
* DP 思路解析看 洛谷 P1004 大佬的题解。
*/
int max(const int a, const int b, const int c, const int d) //单纯 max 函数,没啥好看的。
{ return (a > b ? a : b) > (c > d ? c : d) ? (a > b ? a : b) : (c > d ? c : d); }
main()
{
scanf("%d %d", &m, &n); //这一块都是读入:
for (int y = 0; y < m; y++)
for (int x = 0; x < n; x++)
scanf("%d", &map[x][y]);
//DP 初始化 / 边界:
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dp[0][i][j] = map[0][0]; /* 走 0 步均初始化为 0。
* 已试过 dp[][][] 全填 0 还是 WA。
*/
for (int k = 1; k <= (n + m - 3); k++) /*枚举步数。不枚举到右下角,因为:
* 后面 j 循环从 i+1 开始,但会直接因为 j<n 这个条件结束。
* 因此就算 k 开到 n+m-2 一样算不到右下角。
*/
for (int i = 0; i <= k && i < n; i++) /* 枚举第一张纸条的X坐标。
* i<n 防止越界,i<=k 只走 k 步到不了 i>k 的地方。
*/
for (int j = i + 1; j <= k && j < n; j++) { //从 i+1 开始枚举,保证路径不相交。
dp[k][i][j] = //状态转移方程:
max(dp[k - 1][i][j], dp[k - 1][i - 1][j], dp[k - 1][i][j - 1], dp[k - 1][i - 1][j - 1]) + map[i][k - i] + map[j][k - j];
}
printf("%d\n", dp[n + m - 3][n - 2][n - 1]); /* 输出答案:
* 第一张纸条到 右下点左边一格、
* 第二张纸条到 右下角上面一格 的最优解。
*/
return 0;
}
///:~
顺便贴一下第 1 个 WA 测试点的输入数据(正确答案 12203,我的输出 12284),便于调试:
由于 CSDN 限制提问字数,放在洛谷的云剪贴板里:https://www.luogu.com.cn/paste/pec15lj8。
猜测应该还是有路径重复走了。
还有问题还可以在下面提。