2008年NOIP传纸条题解析：四维动态规划求解矩阵路径问题

一、题目解读

NOIP 2008年的“传纸条”问题（洛谷P1006）要求求解在一个m×n的矩阵中，两名学生分别从左上角和右下角出发，沿不同路径传递纸条，路径上的数字之和即为好感度。题目限制路径不能相交，需找出两人传递纸条时能获得的最大总好感度。该问题本质是求解两条不交叉路径的最优解，属于动态规划经典题型。

二、解题思路

采用四维动态规划（DP）解决该问题。核心思想是定义四维状态dp[i1][j1][i2][j2]，表示学生A走到(i1,j1)、学生B走到(i2,j2)时的最大好感度。由于两人路径独立但需避免重复计算交汇点，通过遍历所有可能的坐标组合，每次从四种前驱状态（上、左、右上、左上）取最大值，并根据是否交汇决定是否叠加当前节点值。这种四维DP巧妙地将双路径问题转化为单一状态转移，有效解决了路径不重叠的约束。

三、解题步骤

1. 数据输入：读取m×n矩阵，存储每个位置的好心程度grid[i][j]。

2. 动态规划初始化：遍历所有可能的(i1,j1,i2,j2)组合，计算每个状态的最大值：

    状态转移方程：dp[i1][j1][i2][j2] = max(四种前驱状态) + 当前节点值。

    交汇处理：若i1=i2且j1=j2（路径交汇），仅加一次当前值；否则叠加两个节点值。

3. 结果输出：最终答案存储在dp[m][n][m][n]，即两人分别到达右下角时的最大和。

四、代码与注释

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 55;
int grid[MAXN][MAXN];  // 存储每个位置的好心程度
int dp[MAXN][MAXN][MAXN][MAXN];  // 四维DP数组

int main() {
    int m, n;
    cin >> m >> n;
    
    // 输入矩阵数据
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> grid[i][j];
        }
    }
    
    // 动态规划处理
    for(int i1 = 1; i1 <= m; i1++) {
        for(int j1 = 1; j1 <= n; j1++) {
            for(int i2 = 1; i2 <= m; i2++) {
                for(int j2 = 1; j2 <= n; j2++) {
                    // 当前最大值来自四种可能的前驱状态
                    int curr = max(
                        max(dp[i1-1][j1][i2-1][j2], dp[i1-1][j1][i2][j2-1]),
                        max(dp[i1][j1-1][i2-1][j2], dp[i1][j1-1][i2][j2-1])
                    );
                    
                    // 如果两条路径走到同一个点，只加一次值
                    if(i1 == i2 && j1 == j2) {
                        dp[i1][j1][i2][j2] = curr + grid[i1][j1];
                    } else {
                        dp[i1][j1][i2][j2] = curr + grid[i1][j1] + grid[i2][j2];
                    }
                }
            }
        }
    }
    
    // 输出结果
    cout << dp[m][n][m][n] << endl;
    
    return 0;
}

五、总结

本文通过四维动态规划方法，高效解决了NOIP 2008“传纸条”问题。关键点在于：

1. 将双路径问题转化为四维状态，降低复杂度；

2. 利用状态转移方程避免路径交汇时的重复计算；

3. 清晰的时间复杂度O(m⁴)，适用于中小规模矩阵。

该解法为动态规划在路径规划问题中的应用提供了经典范例，对算法竞赛选手具有重要参考价值。