标准题解 这是带状态的线性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 时完全不可能。