2000年NOIP提高组方格取数题解（洛谷P1004）：动态规划思路解题
一、题目解读
方格取数（洛谷P1004）是2000年NOIP提高组的经典题目：给定N×N（N≤9）的方格图，部分格子包含正整数，其余为0。需从左上角A出发，向下或向右走两次到达右下角B，每次路径可取走经过格子的数（取后变为0）。求两条路径取数之和的最大值。题目关键在于路径不可重复取数，需处理两次行走的先后顺序与格子状态的动态变化。
二、解题思路
采用四维动态规划解决该问题。核心思想是定义状态f[k][i][j]，表示第k步时，两条路径分别位于(i,j)与(k+2-i, k+2-j)时的最大取数和。通过维护步数k与两人坐标的同步性，巧妙处理路径重合时的取数规则。算法利用动态规划递推求解，避免了暴力枚举的指数级复杂度。
三、解题步骤
1. 输入与预处理：读取方格数据，存储到g数组，非零格子记为有效值。
2. 状态初始化：f初始值设为负无穷，仅起点状态f[0][1][1] = g[1][1]（即两条路径重合于起点）。
3. 动态规划递推：
○ 外层循环遍历步数k（1~2n-2），确保路径同步推进。
○ 内层循环遍历两人坐标i,j（限制在合法范围）。
○ 状态转移方程：val = max(f[k-1][i][j], f[k-1][i-1][j], f[k-1][i][j-1], f[k-1][i-1][j-1])，即从上一状态四个方向转移。
○ 若i=j（路径重合），仅取当前格子g[i][k+2-i]一次；否则取两个格子g[i][k+2-i] + g[j][k+2-j]之和。
4. 输出结果：最终答案存储在f[2n-2][n][n]，即两条路径均到达终点时的最大和。
四、代码与注释
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 15; // 最大方格尺寸
int g[N][N], f[N*2][N][N]; // g存方格数据，f为动态规划状态数组
int main() {
int n, x, y, v; // 输入参数
cin >> n; // 读取方格尺寸
// 输入方格数据
while((cin >> x >> y >> v) && (x || y || v)) {
g[x][y] = v; // 存储非零格子
}
// 初始化动态规划数组（负无穷）
memset(f, -0x3f, sizeof f);
f[0][1][1] = g[1][1]; // 起点状态：两条路径重合于(1,1)，取数g[1][1]
// 动态规划递推
for(int k = 1; k <= 2*n-2; ++k) { // 步数k（总步数为2n-2）
for(int i = 1; i <= min(n, k+1); ++i) { // 路径1坐标i
for(int j = 1; j <= min(n, k+1); ++j) { // 路径2坐标j
int &val = f[k][i][j]; // 当前状态值
val = max({ // 从四个方向转移
f[k-1][i][j], // 路径1不动，路径2向下
f[k-1][i-1][j], // 路径1向右，路径2不动
f[k-1][i][j-1], // 路径1不动，路径2向右
f[k-1][i-1][j-1] // 路径1向右，路径2向右
});
if(i == j) { // 路径重合时，仅取一次数
val += g[i][k+2-i];
} else { // 路径不重合，取两个格子数
val += g[i][k+2-i] + g[j][k+2-j];
}
}
}
}
// 输出最终答案
cout << f[2*n-2][n][n];
return 0;
}五、总结
该解法通过四维动态规划将路径同步与取数限制巧妙结合，利用状态压缩减少维度，有效解决了路径规划与资源重复利用的矛盾。代码简洁高效，核心在于状态定义与转移方程的设计，对动态规划在多路径问题中的应用具有参考价值。在实际竞赛或算法学习中，此类思维可拓展至更多复杂场景。
原创内容 转载请注明出处
