摘花生

题目描述

Hello Kitty 想摘点花生送给她喜欢的米老鼠。她来到一片 $R \times C$ 的网格状花生地（ $1 \leqslant R, C \leqslant 100$ ），从西北角进去、东南角出来，只能向东或向南走，不能向西或向北走。每个交叉点上有一株花生苗（ $0 \leqslant M \leqslant 1000$ ），经过就能摘走上面的全部花生。输入第一行是整数 $T$ （ $1 \leqslant T \leqslant 100$ ），每组数据第一行是 $R$ 和 $C$ ，随后 $R$ 行每行 $C$ 个整数，按从北向南、从西向东的顺序给出每株花生苗上的花生数；对每组数据输出一行，即最多能摘到的花生颗数。

样例：输入 $2$ 组——第一组 $R=2, C=2$ ，两行为 1 1 和 3 4，输出 8；第二组 $R=2, C=3$ ，两行为 2 3 4 和 1 6 5，输出 16（走 $2 \to 3 \to 6 \to 5$ ）。

思路

由于只能向东、向南走，到达格子 $(i,j)$ 的最后一步只能来自上方或左方；设 $dp[i][j]$ 为走到该格能摘到的最大花生数，则 $dp[i][j] = M_{i,j} + \max(dp[i-1][j],\ dp[i][j-1])$ ，边界外视为 $0$ 。逐行逐格递推到东南角即得答案；实现时用一维数组原地滚动——更新前 $dp[j]$ 是上一行的答案（来自上方）、 $dp[j-1]$ 已是本行的答案（来自左方），空间降为 $O(C)$ 。

参考代码

Python 版：

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#!/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 03:16
# update_at: 2026-09-30 03:16

import sys
from collections.abc import Iterator


def pick_max(grid: list[list[int]]) -> int:
    """从西北角走到东南角、只向东南走，最多能摘到的花生数。

    逐行原地滚动：更新到 (r, c) 时，row_dp[c] 还是上一行（来自上方）的答案，
    row_dp[c-1] 已是本行（来自左方）的答案，取较大者加上当前格的花生即可。
    """
    width = len(grid[0])
    row_dp = [0] * width  # 第 -1 行（虚拟）：网格外收获为 0
    for row in grid:
        for c in range(width):
            from_left = row_dp[c - 1] if c else 0
            row_dp[c] = row[c] + max(row_dp[c], from_left)
    return row_dp[-1]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        R, C = next(data), next(data)
        grid = [[next(data) for _ in range(C)] for _ in range(R)]
        out.append(str(pick_max(grid)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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 08:04
 * update_at: 2026-10-05 08:04
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

typedef long long ll;

ll T;               // 数据组数
ll R, C;            // 花生地的行数、列数
ll m[MAXN][MAXN];   // m[i][j]：格子 (i, j) 上的花生数
ll dp[MAXN];        // 一维滚动数组：更新到 dp[j] 前，dp[j] 是上一行的答案（来自上方），dp[j-1] 是本行左边的答案

// 读取一组花生地，并把 dp 数组清成"虚拟第 0 行"（全 0，网格外收获为 0）。
void read_input() {
    cin >> R >> C;
    for (ll i = 1; i <= R; i++) {
        for (ll j = 1; j <= C; j++) {
            cin >> m[i][j];
        }
    }
    for (ll j = 1; j <= C; j++) dp[j] = 0;
}

// 网格 DP：只能向东、向南走，dp[i][j] = m[i][j] + max(上方 dp, 左方 dp)。
// 首行只能从左方来、首列只能从上方来，边界全 0 后转移式自动覆盖，不用单独处理。
void solve() {
    for (ll i = 1; i <= R; i++) {
        for (ll j = 1; j <= C; j++) {
            ll best = dp[j]; // 来自上方
            if (j > 1 && dp[j - 1] > best) best = dp[j - 1]; // 来自左方
            dp[j] = best + m[i][j];
        }
    }
    cout << dp[C] << "\n";
}

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

    cin >> T;
    while (T--) {
        read_input();
        solve();
    }

    return 0;
}

目录

题目描述

思路

参考代码