形式化题目

给定 $n \times m$ 矩阵，元素 $a_{ij}$ 为非负整数。游戏进行 $m$ 轮，每轮：

1. 从每一行恰好取走一个元素（共 $n$ 个），取走的必须是该行当前的行首或行尾；
2. 本轮得分 = 本轮取走的所有元素之和 $\times 2^i$，其中 $i$ 为轮次编号，从 $1$ 开始。

总得分为 $m$ 轮得分之和，求总得分的最大值。

样例 1（$n = 2, m = 3$，矩阵第一行 1 2 3、第二行 3 4 2），输出 $82$：

合计 $6 + 20 + 56 = 82$。其余样例：单行 4 5 0 5 输出 $122$；两行各 10 个元素的样例输出 $316994$。

正解

思路

一句话本质：先用"行间独立"把 $n$ 行拆成 $n$ 个单行问题，再对每行做"两端取数、权重随轮次指数增长"的区间 DP，最后求和。

朴素做法与瓶颈。 最直接的想法是枚举取数方案：每行每轮有取行首/行尾两种选择，单行方案数 $2^m$（$m = 80$ 时 $\approx 1.2 \times 10^{24}$），行间再组合更是 $2^{nm}$。两层瓶颈不同：

1. 行间组合是乘法爆炸，但可以直接砍掉——每轮每行恰好取走一个元素、权重 $2^i$ 与行无关，所以总得分恒等于各行得分之和，某行取左取右不改变其他行的剩余段与轮次。于是 $n$ 行互相独立，逐行求最优再相加即全局最优。
2. 单行枚举的瓶颈是子问题重叠——不同的左右端选择序列会在中途收敛到同一个剩余段 $a[l..r]$（先取左再取右与先取右再取左可以到达同一段），到达同一段的路径有组合数那么多条，而"把该段取完的最优得分"只由段本身决定：此刻轮次 $pick = m - (r - l)$（此前两侧共取走 $m - (r - l + 1)$ 个元素，本次是下一轮）只依赖段长，与怎么到达无关。指数条路径只对应 $O(m^2)$ 个状态，逐个枚举纯属重复计算。

关键观察：剩余段就是完整的状态。 取走行首后剩余 $[l+1..r]$、取走行尾后剩余 $[l..r-1]$，段长减 1、轮次加 1，未来只取决于新剩余段本身，无后效性成立。于是对每行定义区间 DP：

• 边界：只剩一个元素时两侧已取走 $m-1$ 个，正是第 $m$ 轮，$dp[i][i] = a_i \times 2^m$；
• 转移（$l < r$，令 $pick = m - (r - l)$，本次必取行首或行尾，二选一）：

• 计算顺序：段长从小到大，两个子段段长都减 1、必已算出；
• 答案：每行取 $dp[0][m-1]$（0-based），对 $n$ 行求和。

样例的 DP 表。 下表是样例第 1 行 1 2 3（$m = 3$）的完整 $dp[l][r]$（行 = $l$，列 = $r$，1-based；- 表示 $l > r$ 的无效格；单元格 = 剩余段 $[l..r]$ 取完的最高得分）：

观察重点：对角线是边界 $a_i \times 2^3$（如 $dp[3][3] = 3 \times 8 = 24$）；段长 2 的格子轮次为 $pick = 3 - (2-1) = 2$，如 $dp[1][2]$ 的两候选是"取行首 $1 \times 2^2 + dp[2][2] = 20$"与"取行尾 $2 \times 2^2 + dp[1][1] = 16$"，取 max 得 20。最后一格 $dp[1][3]$（$pick = 1$）的两个候选：

第 2 行 3 4 2 同法算得 $dp[1][3] = 48$（最后一格在"取行首 3 得 46"与"取行尾 2 得 48"间取 48，对应顺序 2, 3, 4）。总分 $34 + 48 = 82$，与题面逐轮解释吻合。

正确性。 对剩余段长归纳：长度 1 时唯一元素必在第 $m$ 轮被取，边界正确；一般情形下，题面规定本次只能取行首或行尾，两个候选恰好枚举全部合法第一步，取走后进入更短的段（轮次自动加 1，与状态定义一致），由归纳假设两分支内部各自最优，max 即该段最优。行间独立性保证各行最优可直接相加，覆盖所有全局方案且不重不漏。

边界与溢出。 $m = 1$ 时直接输出 $a \times 2$；元素可为 $0$ 不影响转移。答案上界约为 $80 \times 1000 \times 2^{81} \approx 1.9 \times 10^{29}$，超出 64 位整数——原题的 C++ 标程必须配高精度，而 Python 的 int 是任意精度，直接用 << pick 乘权重即可。数据范围 $n, m \leqslant 80$ 对应转移次数约 $2.5 \times 10^5$，见下文复杂度。

代码

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#!/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-09-30 19:17
# update_at: 2026-09-30 19:24

import sys


def row_best(row: list[int]) -> int:
    """单行取数：dp[l][r] = 剩余段为 row[l..r] 时取完该段的最高得分。"""
    m = len(row)
    dp = [[0] * m for _ in range(m)]
    for i in range(m):
        dp[i][i] = row[i] << m  # 只剩一个元素，已是第 m 轮，得分为 元素 × 2^m
    for length in range(2, m + 1):  # 剩余段按长度递推，长段只依赖短段
        for l in range(m - length + 1):
            r = l + length - 1
            pick = m - r + l  # 剩余段长 r-l+1，此前两侧共取走 m-(r-l+1) 个，本次是第 pick 轮
            # 行首或行尾二选一，取走的元素乘本轮权重 2^pick
            dp[l][r] = max(dp[l + 1][r] + (row[l] << pick), dp[l][r - 1] + (row[r] << pick))
    return dp[0][m - 1]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    # 各行取数互不影响，总分就是每行独立最优之和；答案可达 2^80 量级，Python 大整数直接存
    print(sum(row_best([next(data) for _ in range(m)]) for _ in range(n)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
79
80
81
82
83
84
85/**
 * 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-05 09:42
 * update_at: 2026-10-05 09:42
 */
// roj/1574 矩阵取数游戏：行间独立，逐行做两端取数的区间 DP。
// 答案上界约 80*1000*2^81 < 2^98，超过 64 位但远小于 2^128，用 __int128 承接。
#include <cstdio>

typedef long long ll;

const int MAXM = 85; // m <= 80，dp 表按单行最大长度开

ll a[MAXM];               // 当前行的元素，a[1..m] 对应题面从左到右
__int128 dp[MAXM][MAXM];  // dp[l][r]：把当前行剩余段 a[l..r] 取完能得到的最高得分
ll n, m;

// 输出 __int128：答案约 1.9e29，用扩展整数承接，省去手写高精度。
void print_int128(__int128 x) {
    if (x == 0) {
        putchar('0');
        putchar('\n');
        return;
    }
    char buf[64];
    int len = 0;
    while (x > 0) {
        int digit = x % 10;
        buf[len] = '0' + digit;
        len++;
        x /= 10;
    }
    while (len > 0) {
        len--;
        putchar(buf[len]);
    }
    putchar('\n');
}

// 单行最优得分：剩余段长度从 1 递推到 m，长段只依赖短段。
__int128 row_best() {
    for (int i = 1; i <= m; i++) {
        // 只剩一个元素时两侧已取走 m-1 个，它必是第 m 轮，权重 2^m
        __int128 weight = 1;
        weight = weight << m;
        dp[i][i] = weight * a[i];
    }
    for (int len = 2; len <= m; len++) {
        for (int l = 1; l + len - 1 <= m; l++) {
            int r = l + len - 1;
            int pick = m - (r - l); // 本次是第 pick 轮，轮次只由剩余段长度决定
            __int128 weight = 1;
            weight = weight << pick;
            // 本次只能取行首或行尾，两种取法各自加上剩余段的最优得分
            __int128 take_left = dp[l + 1][r] + weight * a[l];
            __int128 take_right = dp[l][r - 1] + weight * a[r];
            if (take_left > take_right) {
                dp[l][r] = take_left;
            } else {
                dp[l][r] = take_right;
            }
        }
    }
    return dp[1][m];
}

void solve() {
    scanf("%lld %lld", &n, &m);
    __int128 answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%lld", &a[j]);
        }
        // 每轮每行各取一个、权重只与轮次有关，各行互不影响，总分即各行最优之和
        answer = answer + row_best();
    }
    print_int128(answer);
}

int main() {
    solve();
    return 0;
}

复杂度

• 时间复杂度：$O(n m^2)$。单行是"段长 $\times$ 左端点"两重循环、每格 $O(1)$ 转移，$n = m = 80$ 时全程约 $2.5 \times 10^5$ 次转移，每次是几百比特的大整数加法，本地实测单例最大 0.062 s，在 1000 ms 内绰绰有余；与标准 C++ 正解同阶，没有退化成暴力。
• 空间复杂度：$O(m^2)$。单行 dp 表 $80 \times 80 = 6400$ 格，逐行复用，加上一次性读入的 $n \times m$ 个整数，实测峰值约 15.4 MB，远低于 128 MB。

总结

• 行间独立是本题的第一刀：每轮每行各取一个、权重只看轮次，总得分 = 各行得分之和，$n$ 个耦合决策塌缩成 $n$ 个独立子问题。
• 单行是经典的两端取数区间 DP：状态 $dp[l][r]$ = 剩余段取完的最优得分，轮次 $pick = m - (r-l)$ 只由段长决定，所以轮次不必进状态，状态数停在 $O(m^2)$。
• 按段长递增递推保证子状态先算出；两候选转移恰好对应"取行首/取行尾"的全部可能，归纳即正确性。
• 权重 $2^{pick}$ 用左移、答案约 $10^{29}$ 用 Python 原生大整数——这题在 C++ 里要配高精度，是选 Python 落地的天然优势。

图示解析

这张图串起本题从"枚举爆炸"到"求和答案"的推导主线：

1
2
3
4
5枚举全部取法：2^(nm) 组合
 `- 行间独立：总分 = 各行得分之和（每轮每行各取一个、权重同轮次）
    `- 单行剩余段 [l..r] 就是完整状态（轮次 pick = m-(r-l) 只看段长）
       `- 区间 DP：取行首 / 取行尾 两候选取 max，按段长递推
          `- 逐行取 dp[0][m-1] 求和 → 最大总得分

先看每层节点排除了什么（行间组合、轮次维度、路径枚举），再顺着分支确认剩下的状态数只有 $O(m^2)$；图中只保留正文已证明的关键关系，逐轮样例核对以上文 DP 表为准。