大盗阿福

题目描述

一条街有 $N$ 家店铺，每家有一定现金。阿福要洗劫其中若干家，但不能同时洗劫相邻两家，否则报警。求最多能拿到的现金。

输入第一行为整数 $T$ （ $T\le 50$ ），表示数据组数。每组数据第一行为 $N$ （ $1\le N\le 100\,000$ ），第二行为 $N$ 个不超过 $1000$ 的正整数。

对每组数据输出一行最大现金数。

样例输入：

text

样例输出：

text

1
28
24

思路

设 $f[i]$ 为前 $i$ 家店铺的最大收益。第 $i$ 家可以不选，则 $f[i]=f[i-1]$ ；可以选，则第 $i-1$ 家不能选， $f[i]=f[i-2]+a_i$ 。转移方程 $f[i]=\max(f[i-1],f[i-2]+a_i)$ ，用两个变量滚动即可。

参考代码

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

import sys
from collections.abc import Iterator


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

    for _ in range(T):
        n = next(data)
        vals: Iterator[int] = (next(data) for _ in range(n))

        # 滚动 DP：prev2 = f[i-2]，prev1 = f[i-1]，当前格可选可不选。
        prev2, prev1 = 0, next(vals) if n else 0
        for x in vals:
            prev2, prev1 = prev1, max(prev1, prev2 + x)

        out.append(str(prev1))

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

typedef long long ll;

const int MAXN = 100000 + 5; // 每组数据最多 N 家店铺

ll a[MAXN]; // 每家店铺的现金

// 滚动 DP：prev2 表示 f[i-2]，prev1 表示 f[i-1]
ll solve_case(int n) {
    ll prev2 = 0;       // f[0] = 0
    ll prev1 = a[1];    // f[1] = a[1]
    for (int i = 2; i <= n; i++) {
        ll cur = max(prev1, prev2 + a[i]); // 不选第 i 家 或 选第 i 家
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
        }
        if (n == 0) {
            printf("0\n");
            continue;
        }
        printf("%lld\n", solve_case(n));
    }
    return 0;
}

目录

题目描述

思路

参考代码