P1006 传纸条

May 4, 2026 · 7 分钟阅读 · 动态规划 ·

文章目录

题目信息

字段	内容
题号	P1006
难度	绿题（普及+）
知识点	动态规划、方格 DP

题目描述

小渊和小轩是好朋友，他们在一起总有谈不完的话题。
一次素质拓展活动中，班上同学安排坐成一个 m 行 n 列的矩阵，小渊坐在矩阵的左上角，坐标 (1,1)；小轩坐在矩阵的右下角，坐标 (m,n)。

从小渊到小轩的纸条可以向下或向右传递；从小轩到小渊的纸条可以向上或向左传递（本质上仍是两条从左上到右下的不相交路径）。

他们希望对他们的友好指数进行量化评估。评估方法为：找出两条从小渊到小轩的传递路径（可以重合，但同格指数只算一次），使得路径上同学的友好指数之和最大。

输入格式：

第一行两个整数 m 和 n，表示矩阵有 m 行、n 列（1 ≤ m, n ≤ 50）。

接下来 m 行，每行 n 个整数，表示每位同学的友好指数（0 ≤ 指数 ≤ 10000）。

输出格式：

一个整数，表示两条路径上友好指数之和的最大值。

样例：

输入

输出

样例解释：

两条最优路径分别为：

路径一（从小渊到小轩）：(1,1) → (1,2) → (1,3) → (2,3) → (3,3)，指数和 = 0 + 3 + 9 + 5 + 0 = 17
路径二（从小轩到小渊，同样从左上到右下处理）：(1,1) → (2,1) → (2,2) → (3,2) → (3,3)，指数和 = 0 + 2 + 8 + 7 + 0 = 17

总和 = 34。注意坐标 (1,1) 和 (3,3) 被两条路径共享，指数只计算一次。

解题思路

核心思想：四维动态规划

这是经典的「方格取数 / 传纸条」问题，可以用四维 DP 同时描述两条路径的状态。

状态定义

dp[i][j][k][l] 表示：第一条路径走到 (i, j)，第二条路径走到 (k, l) 时，两条路径的友好指数之和的最大值。

状态转移

每一步两条路径各走一步，各有两种走法（向下 / 向右），共 4 种组合：

① dp[i-1][j][k-1][l]   第一条向下，第二条向下
② dp[i-1][j][k][l-1]   第一条向下，第二条向右
③ dp[i][j-1][k-1][l]   第一条向右，第二条向下
④ dp[i][j-1][k][l-1]   第一条向右，第二条向右

取四个方向的最大值，再加上当前格子的友好指数（若两路径处于同一格，只加一次）。

去重（同一格子只算一次）

如果 i == k && j == l，说明两条路径当前走到了同一格子，这个格子的友好指数只需加一次。

dp[i][j][k][l] = best + a[i][j] + a[k][l];
if (i == k && j == l) {
    dp[i][j][k][l] -= a[i][j];  // 同一格只算一次
}

初始化

起点 dp[1][1][1][1] 初始化为 a[1][1]，其余初始为负无穷大，表示「不可达」。

完整代码

C++（四维 DP）

#include <bits/stdc++.h>
using namespace std;

const int kMaxN = 55;
const int kNegInf = -0x3f3f3f3f;

int dp[kMaxN][kMaxN][kMaxN][kMaxN];
int a[kMaxN][kMaxN];
int m, n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }

    // 初始化为负无穷，表示不可达
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= m; k++) {
                for (int l = 0; l <= n; l++) {
                    dp[i][j][k][l] = kNegInf;
                }
            }
        }
    }
    dp[1][1][1][1] = a[1][1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= m; k++) {
                for (int l = 1; l <= n; l++) {
                    if (i == 1 && j == 1 && k == 1 && l == 1) continue;

                    int best = max({
                        dp[i - 1][j][k - 1][l],
                        dp[i - 1][j][k][l - 1],
                        dp[i][j - 1][k - 1][l],
                        dp[i][j - 1][k][l - 1]
                    });

                    dp[i][j][k][l] = best + a[i][j] + a[k][l];
                    if (i == k && j == l) {
                        dp[i][j][k][l] -= a[i][j];  // 同一格只算一次
                    }
                }
            }
        }
    }

    cout << dp[m][n][m][n] << "\n";
    return 0;
}

关键代码讲解

四维 DP 的状态转移

int best = max({
    dp[i - 1][j][k - 1][l],     // 下、下
    dp[i - 1][j][k][l - 1],     // 下、右
    dp[i][j - 1][k - 1][l],    // 右、下
    dp[i][j - 1][k][l - 1]     // 右、右
});

四种转移分别对应：

第一条路径向下 (i-1, j)，第二条路径向下 (k-1, l)
第一条路径向下 (i-1, j)，第二条路径向右 (k, l-1)
第一条路径向右 (i, j-1)，第二条路径向下 (k-1, l)
第一条路径向右 (i, j-1)，第二条路径向右 (k, l-1)

同一格去重

if (i == k && j == l) {
    dp[i][j][k][l] -= a[i][j];
}

两条路径走到同一个格子时，a[i][j] 被加了两次（a[i][j] + a[k][l] 当 i==k && j==l 就是 2*a[i][j]），所以需要减去一次。

复杂度分析

指标	复杂度
时间复杂度	O(m² × n²)，`m,n ≤ 50` 时约为 6.25 × 10⁶
空间复杂度	O(m² × n²)，约需 6.25 MB

洛谷数据 m, n ≤ 50，完全在限制范围内。

易错点

初始化为负无穷：未到达的状态必须初始化为极小值，否则 max() 会错误地取到未更新的 0。
同一格去重：if (i == k && j == l) 必须判断，否则同一格子的友好指数会被重复计入。
起点跳过：dp[1][1][1][1] 已在循环外初始化，循环内应跳过，避免被负无穷覆盖。
行列边界：i-1、j-1、k-1、l-1 必须保证不小于 1，但由于 dp[0][...] 等初始化为负无穷，不会被选为 best，可以放心使用。

其他语言解法

Java（四维 DP）

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    private static final class FastScanner {
        private final BufferedInputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0;
        private int len = 0;

        FastScanner() {
            in = new BufferedInputStream(System.in);
        }

        private int readByte() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c, sign = 1, res = 0;
            do {
                c = readByte();
            } while (c <= ' ' && c != -1);
            if (c == '-') {
                sign = -1;
                c = readByte();
            }
            while (c > ' ') {
                res = res * 10 + (c - '0');
                c = readByte();
            }
            return res * sign;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        int m = fs.nextInt();
        int n = fs.nextInt();

        int[][] a = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                a[i][j] = fs.nextInt();
            }
        }

        final int NEG_INF = -0x3f3f3f3f;
        int[][][][] dp = new int[m + 1][n + 1][m + 1][n + 1];
        for (int i = 0; i <= m; i++)
            for (int j = 0; j <= n; j++)
                for (int k = 0; k <= m; k++)
                    for (int l = 0; l <= n; l++)
                        dp[i][j][k][l] = NEG_INF;

        dp[1][1][1][1] = a[1][1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= m; k++) {
                    for (int l = 1; l <= n; l++) {
                        if (i == 1 && j == 1 && k == 1 && l == 1) continue;
                        int best = Math.max(
                            Math.max(dp[i - 1][j][k - 1][l], dp[i - 1][j][k][l - 1]),
                            Math.max(dp[i][j - 1][k - 1][l], dp[i][j - 1][k][l - 1])
                        );
                        dp[i][j][k][l] = best + a[i][j] + a[k][l];
                        if (i == k && j == l) {
                            dp[i][j][k][l] -= a[i][j];
                        }
                    }
                }
            }
        }

        System.out.println(dp[m][n][m][n]);
    }
}

Go（四维 DP）

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

func max4(a, b, c, d int) int {
    return max(max(a, b), max(c, d))
}

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)

    scanner.Scan()
    m, _ := strconv.Atoi(scanner.Text())
    scanner.Scan()
    n, _ := strconv.Atoi(scanner.Text())

    a := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        a[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            scanner.Scan()
            a[i][j], _ = strconv.Atoi(scanner.Text())
        }
    }

    const NEG_INF = -0x3f3f3f3f
    dp := make([][][][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([][][]int, n+1)
        for j := 0; j <= n; j++ {
            dp[i][j] = make([][]int, m+1)
            for k := 0; k <= m; k++ {
                dp[i][j][k] = make([]int, n+1)
                for l := 0; l <= n; l++ {
                    dp[i][j][k][l] = NEG_INF
                }
            }
        }
    }
    dp[1][1][1][1] = a[1][1]

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            for k := 1; k <= m; k++ {
                for l := 1; l <= n; l++ {
                    if i == 1 && j == 1 && k == 1 && l == 1 {
                        continue
                    }
                    best := max4(
                        dp[i-1][j][k-1][l],
                        dp[i-1][j][k][l-1],
                        dp[i][j-1][k-1][l],
                        dp[i][j-1][k][l-1],
                    )
                    dp[i][j][k][l] = best + a[i][j] + a[k][l]
                    if i == k && j == l {
                        dp[i][j][k][l] -= a[i][j]
                    }
                }
            }
        }
    }

    fmt.Println(dp[m][n][m][n])
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

JavaScript（四维 DP）

'use strict';

const fs = require('fs');
const data = fs.readFileSync('/dev/stdin', 'utf8');
const tokens = data.trim().split(/\s+/).map(Number);
let idx = 0;

const m = tokens[idx++];
const n = tokens[idx++];
const a = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
        a[i][j] = tokens[idx++];
    }
}

const NEG_INF = -0x3f3f3f3f;
const dp = Array.from({ length: m + 1 }, () =>
    Array.from({ length: n + 1 }, () =>
        Array.from({ length: m + 1 }, () =>
            Array(n + 1).fill(NEG_INF)
        )
    )
);
dp[1][1][1][1] = a[1][1];

for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
        for (let k = 1; k <= m; k++) {
            for (let l = 1; l <= n; l++) {
                if (i === 1 && j === 1 && k === 1 && l === 1) continue;
                const best = Math.max(
                    dp[i - 1][j][k - 1][l],
                    dp[i - 1][j][k][l - 1],
                    dp[i][j - 1][k - 1][l],
                    dp[i][j - 1][k][l - 1]
                );
                dp[i][j][k][l] = best + a[i][j] + a[k][l];
                if (i === k && j === l) {
                    dp[i][j][k][l] -= a[i][j];
                }
            }
        }
    }
}

console.log(dp[m][n][m][n]);