[NOIP2007-提高] 矩阵取数游戏

形式化题目

给定 $n \times m$ 非负整数矩阵，进行 $m$ 轮取数：每轮从每一行各取走一个元素，且只能取该行当前的行首或行尾；第 $i$ 轮得分为（本轮取走的 $n$ 个元素之和） $\times 2^i$ （轮次 $i$ 从 1 编号）。求所有合法取法中的最大总得分。

样例（ $n=2, m=3$ ）：

text

1
2
3
4输入：          输出：
2 3             82
1 2 3
3 4 2

一种最优取法：第一行依次取 $1,2,3$ ，得分 $1\times2+2\times4+3\times8=34$ ；第二行依次取 $2,3,4$ （先取行尾的 2），得分 $2\times2+3\times4+4\times8=48$ 。合计 $34+48=82$ 。注意答案随轮次指数放大： $m=80$ 时最大总得分约为 $10^{31}$ ，远超 64 位整数范围——这正是本题选 Python 原生大整数的天然优势。

正解

思路

朴素做法与瓶颈。 一行的取法由 $m-1$ 个"取左/取右"决定，共 $2^{m-1}$ 种； $n$ 行组合起来是 $2^{n(m-1)}$ 条路径，暴力枚举不可行。要压缩状态，先找两层结构。

观察一：行间独立。 把总得分按行重新分组：

\text{总分}=\sum_{i=1}^{m}2^i\Big(\sum_{r=1}^{n}a_{r,i_r}\Big) =\sum_{r=1}^{n}\underbrace{\sum_{i=1}^{m}2^i\,a_{r,i_r}}_{\text{第 }r\text{ 行自己的得分}}

每轮每行恰好取一个元素，所以第 $r$ 行第 $k$ 次被取的元素必然发生在第 $k$ 轮、权重 $2^k$ ；两行的取法互不影响对方。于是问题拆成 $n$ 个独立的单行问题，最后把各行最优值相加。

观察二：行内是区间 DP。 对一行，取数永远发生在两端，取走一些元素后剩余部分仍是一段连续区间；且剩余区间 $[l,r]$ 的长度唯一决定下一次取数的轮次 $k=m-r+l$ （已取 $m-(r-l+1)$ 个，本次是第 $k$ 次，权重 $2^k$ ）。因此只需一维区间状态：

dp[l][r]=\max\big(a_l\cdot 2^{k}+dp[l+1][r],\ \ a_r\cdot 2^{k}+dp[l][r-1]\big),\quad k=m-r+l

边界是只剩一个元素的情形：它必然在第 $m$ 轮被取， $dp[i][i]=a_i\cdot 2^m$ 。按区间长度递增计算（代码中 $l$ 从右往左、 $r$ 从左往右），保证两个子区间先算出。

样例第一行 $[1,2,3]$ 的完整 DP 表（ $m=3$ ，展示全部 6 个状态的轮次与两种选择）：

剩余区间 $[l,r]$	含义	本次轮次 $k$	取行首： $a_l\cdot 2^k+dp[l+1][r]$	取行尾： $a_r\cdot 2^k+dp[l][r-1]$	$dp[l][r]$
$[0,0]$	只剩 1	3	—	—	$1\times8=8$
$[1,1]$	只剩 2	3	—	—	$2\times8=16$
$[2,2]$	只剩 3	3	—	—	$3\times8=24$
$[0,1]$	剩 1,2	2	$1\times4+16=20$	$2\times4+8=16$	$20$
$[1,2]$	剩 2,3	2	$2\times4+24=32$	$3\times4+16=28$	$32$
$[0,2]$	全部剩余	1	$1\times2+32=\mathbf{34}$	$3\times2+20=26$	$34$

表中先填对角线（单元素边界），再按区间长度递增填 $[0,1]\to[1,2]\to[0,2]$ 。第一行最优得分为 34（第 1 轮取 1、第 2 轮取 2、第 3 轮取 3）；同法算出第二行 $[3,4,2]$ 最优 48（第 1 轮取行尾的 2，再取 3、4），总分 $34+48=82$ ，与样例吻合。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 十进制大整数（little-endian），支持加法/乘法/比较
struct BigInt {
    vector<int> d;
    BigInt() { d.push_back(0); }
    BigInt(ll x) { d.clear(); if (x == 0) d.push_back(0); else while (x) { d.push_back((int)(x % 10)); x /= 10; } }
    void trim() { while (d.size() > 1 && d.back() == 0) d.pop_back(); }
    bool is_zero() const { return d.size() == 1 && d[0] == 0; }
    int cmp(const BigInt& o) const {
        if (d.size() != o.d.size()) return d.size() < o.d.size() ? -1 : 1;
        for (int i = (int)d.size() - 1; i >= 0; i--)
            if (d[i] != o.d[i]) return d[i] < o.d[i] ? -1 : 1;
        return 0;
    }
    bool operator<(const BigInt& o) const { return cmp(o) < 0; }
    string str() const { string r; for (int i = (int)d.size() - 1; i >= 0; i--) r += char('0' + d[i]); return r; }
    BigInt operator+(const BigInt& o) const {
        BigInt r; r.d.assign(max(d.size(), o.d.size()) + 1, 0);
        for (size_t i = 0; i < d.size(); i++) r.d[i] += d[i];
        for (size_t i = 0; i < o.d.size(); i++) r.d[i] += o.d[i];
        for (size_t i = 0; i + 1 < r.d.size(); i++) { r.d[i + 1] += r.d[i] / 10; r.d[i] %= 10; }
        r.trim(); return r;
    }
    BigInt operator*(const BigInt& o) const {
        BigInt r; r.d.assign(d.size() + o.d.size(), 0);
        for (size_t i = 0; i < d.size(); i++)
            for (size_t j = 0; j < o.d.size(); j++)
                r.d[i + j] += d[i] * o.d[j];
        for (size_t i = 0; i + 1 < r.d.size(); i++) { r.d[i + 1] += r.d[i] / 10; r.d[i] %= 10; }
        r.trim(); return r;
    }
};

int n, m;
ll row[85];
BigInt pow2[85];   // pow2[i] = 2^i

BigInt row_score() {
    // dp[l][r]：还剩 [l,r] 未取时已拿到的最高分
    static BigInt dp[85][85];
    for (int l = m - 1; l >= 0; l--) {
        dp[l][l] = pow2[m] * row[l];
        for (int r = l + 1; r < m; r++) {
            int shift = m - r + l;
            BigInt take_left = pow2[shift] * row[l] + dp[l + 1][r];
            BigInt take_right = pow2[shift] * row[r] + dp[l][r - 1];
            dp[l][r] = take_left < take_right ? take_right : take_left;
        }
    }
    return dp[0][m - 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    pow2[0] = BigInt(1);
    for (int i = 1; i <= m; i++) pow2[i] = pow2[i - 1] * BigInt(2);

    BigInt total(0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cin >> row[j];
        total = total + row_score();
    }
    cout << total.str() << "\n";
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 07:37
# update_at: 2026-10-02 07:37

import sys


def row_score(row: list[int]) -> int:
    """一行取数的最大得分：dp[l][r] 表示还剩 [l,r] 未取时，这一行已拿到的最高分。

    第 k 次取的权重是 2^k；区间长 L 时已取 m-L 个，本次是第 m-L+1 次取，
    所以权重 = 2^(m-L+1) = row 元素左移 (m-r+l) 位。
    """
    m = len(row)
    dp = [[0] * m for _ in range(m)]
    for l in range(m - 1, -1, -1):
        dp[l][l] = row[l] << m  # 只剩一个时它是第 m 次被取
        for r in range(l + 1, m):
            shift = m - r + l  # 本次取数的轮次编号
            take_left = (row[l] << shift) + dp[l + 1][r]   # 取行首，剩 [l+1,r]
            take_right = (row[r] << shift) + dp[l][r - 1]   # 取行尾，剩 [l,r-1]
            dp[l][r] = max(take_left, take_right)
    return dp[0][m - 1]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    # 各行独立（每行权重序列相同），总分 = 各行最优得分之和
    total = 0
    for _ in range(n):
        row = [next(data) for _ in range(m)]
        total += row_score(row)

    print(total)


if __name__ == "__main__":
    solve()

复杂度

时间：单行 $O(m^2)$ 个状态、每个状态 $O(1)$ 转移， $n$ 行合计 $O(nm^2)$ ， $n=m=80$ 时约 $5.1\times10^5$ 次大整数运算，与 C++ 正解同阶。
空间：单行 $m\times m$ 的 dp 表，各行复用后丢弃，合计 $O(m^2)$ 。
C++ 落地时答案上界约 $2^{103}$ ，需 unsigned __int128 或高精度； Python 的 int 任意精度，x << k 即完成 $\times 2^k$ 。

总结

本题两步拆解：先按"每轮得分对行求和是线性的"把矩阵游戏拆成 $n$ 个独立单行问题，再对单行发现"剩余部分始终是连续区间、区间长度决定取数轮次"，用区间 DP 把 $2^{m-1}$ 条取法压到 $O(m^2)$ 个状态。行间独立 + 行内区间 DP，总复杂度 $O(nm^2)$ ；指数级放大的答案交给 Python 原生大整数，shift = m - r + l 一行同时表达轮次与权重。

[NOIP2007-提高] 矩阵取数游戏

目录

形式化题目

正解

思路

代码

复杂度

总结