📝 题目大意

这是一道经典“打家劫舍”问题的变体。在原版问题中，相邻的房屋绝对不能同时被偷。而在本题中，相邻房屋可以同时被偷，但会受到收益折损的惩罚。 具体来说，对于房屋 $i$，它的实际收益取决于它本身以及它左邻居（$i-1$）和右邻居（$i+1$）的被偷状态：

• 如果当前房屋不偷，收益为 $0$；
• 如果当前房屋偷了：
  • 左右邻居都没偷，拿满收益 $a[i]$；
  • 左右邻居恰好有一个被偷，收益减半 $\lfloor a[i] / 2 \rfloor$；
  • 左右邻居都被偷，收益只有 $\lfloor a[i] / 3 \rfloor$。

目标是在这一规则下，求整个街区 $N$ 个房屋能获取的最大总收益。

---

💡 解题思路

因为每个房屋 $i$ 的收益仅受到其相邻两个房屋状态的影响，这是一个具有局部依赖性质的最优化问题，非常适合使用动态规划 (Dynamic Programming) 来解决。

1. 状态定义

在传统的打家劫舍中，我们只需要记录“当前房屋偷或不偷”。但在这里，计算第 $i$ 个房屋的具体收益时，还需要知道第 $i-1$ 个房屋和第 $i+1$ 个房屋的状态。 为了解决“需要知道未来状态”的问题，我们可以在当前步骤提前枚举下一个房屋的状态。

定义 dp[i][x][y] 为： 处理完前 $i$ 个房屋，且强制第 $i$ 个房屋的状态为 $x$（$0$ 表示不偷，$1$ 表示偷），第 $i+1$ 个房屋的状态为 $y$ 时的最大总收益。

2. 状态转移

当我们从第 $i-1$ 个房屋推导到第 $i$ 个房屋时，我们假设第 $i-1$ 个房屋的状态为 $z$。 此时，房屋 $i$ 的收益 cost(i, z, x, y) 就完全确定了：

• 若 $x = 0$，cost = 0
• 若 $x = 1$：
  • 若 $z = 1$ 且 $y = 1$，cost = a[i] / 3
  • 若 $z = 1$ 或 $y = 1$，cost = a[i] / 2
  • 否则 cost = a[i]

那么转移方程为：

$$dp[i][x][y] = \max_{z \in \{0,1\}} \Big( dp[i-1][z][x] + cost(i, z, x, y) \Big)$$

(注意：上一轮的当前房屋 $x$ 变成了这一轮的过去房屋，所以上一轮的状态是 dp[i-1][z][x])

3. 边界与答案

• 初始状态：对于第 1 个房屋，它没有左邻居（可以看作 $z=0$），直接初始化 dp[1][x][y] = cost(1, 0, x, y)。
• 最终答案：推导到第 $N$ 个房屋时，由于不存在第 $N+1$ 个房屋，所以第 $N+1$ 个房屋的状态 $y$ 只能为 $0$。因此最终答案为 $\max(dp[N][0][0], dp[N][1][0])$。
• 空间优化：注意到 dp[i] 的计算只依赖于 dp[i-1]，所以我们可以使用滚动数组，把第一维空间优化掉。

---

⏱️ 复杂度分析

• 时间复杂度：$\mathcal{O}(N)$。外层循环遍历 $N$ 个房屋，内层有 $x, y, z$ 的三种 $0/1$ 状态组合，每个房屋只需进行 $2 \times 2 \times 2 = 8$ 次常数级别的运算，时间极其高效。
• 空间复杂度：$\mathcal{O}(N)$。由于使用了滚动数组，DP 状态数组的大小为 $\mathcal{O}(1)$（仅为 $2 \times 2$ 的矩阵）。但是我们需要一个长度为 $N$ 的数组来存储房屋的原始金币数据 $a[i]$，故整体空间复杂度为 $\mathcal{O}(N)$。

---

💻 标准代码 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 优化输入输出流速度，防止大数据量下 TLE
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    if (!(cin >> n)) return 0;
    
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    
    // 边界情况：没有房屋
    if (n == 0) {
        cout << 0 << "\n";
        return 0;
    }
    
    // dp_prev[x][y] 表示上一轮计算完毕时：
    // 第 i-1 个房子状态为 x，第 i 个房子状态为 y 的最大收益
    long long dp_prev[2][2] = {0};
    long long dp_curr[2][2] = {0};
    
    // 匿名函数：严格按照题目“具体规则”计算房屋 i 的实际收益
    // i: 当前房屋编号 | z: i-1 的状态 | x: i 的状态 | y: i+1 的状态
    auto cost = [&](int i, int z, int x, int y) -> long long {
        if (x == 0) return 0; // 当前房屋不偷，收益为 0
        if (z == 1 && y == 1) return a[i] / 3; // 左右都被偷（C++整数除法自带向下取整）
        if (z == 1 || y == 1) return a[i] / 2; // 只有一边被偷
        return a[i];                           // 左右都没被偷
    };
    
    // 【初始化】处理第 1 个房屋
    // 此时它没有左邻居 (视为 z=0)
    for (int x = 0; x < 2; ++x) { // 第 1 个房子的状态
        for (int y = 0; y < 2; ++y) { // 第 2 个房子的状态
            dp_prev[x][y] = cost(1, 0, x, y);
        }
    }
    
    // 【状态转移】从第 2 个房屋开始 DP，直至第 N 个房屋
    for (int i = 2; i <= n; ++i) {
        for (int x = 0; x < 2; ++x) { // 枚举当前房屋 i 的状态 x
            for (int y = 0; y < 2; ++y) { // 枚举下一个房屋 i+1 的状态 y
                
                // z 是上一个房屋 i-1 的状态
                // 状态转移：在上一个状态的所有合法 z 中取最大值，再加上当前带来的收益
                dp_curr[x][y] = max(
                    dp_prev[0][x] + cost(i, 0, x, y), 
                    dp_prev[1][x] + cost(i, 1, x, y)
                );
            }
        }
        
        // 滚动数组覆盖，准备处理下一座房屋
        for (int x = 0; x < 2; ++x) {
            for (int y = 0; y < 2; ++y) {
                dp_prev[x][y] = dp_curr[x][y];
            }
        }
    }
    
    // 【计算答案】最终处理完前 N 个房屋
    // 第 N+1 个房屋实际不存在，所以其状态 y 必然为 0（没被偷）
    long long ans = max(dp_prev[0][0], dp_prev[1][0]);
    cout << ans << "\n";
    
    return 0;
}

标准题解 这是带状态的线性DP，用 dp[i][0/1/2] 表示前 i 个房屋，第 i 个房屋的状态：

0：没偷

1：偷了，且前一个没偷

2：偷了，且前一个也偷了（需要配合计算收益减半）

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

int main() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    const ll INF = 1e18;
    vector<array<ll, 3>> dp(n + 1);
    dp[0] = {0, -INF, -INF};

    for (int i = 1; i <= n; i++) {
        // 第i间不偷：前一间可以是任意状态
        dp[i][0] = max({dp[i-1][0], dp[i-1][1], dp[i-1][2]});

        // 第i间偷，且前一间没偷：收益全额
        dp[i][1] = dp[i-1][0] + a[i];

        // 第i间偷，且前一间也偷了：收益减半
        dp[i][2] = dp[i-1][1] + a[i] / 2;
    }

    cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl;
    return 0;
}

这个DP的时间复杂度是 O(N)，空间复杂度 O(N) 可优化到 O(1)，暴力枚举所有子集是 O(2^N)，N=10^5 时完全不可能。