python/TangDou/AcWing/Statemachine/1049_1.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int T;          //T组数据
int n;          //每一组数据的个数n
int a[N];       //每个商店的金钱数量
/**
f[i][0]  代表的是不偷第i家店铺能得到的最多现金数量；
f[i][1]  代表的是偷第i家店铺能得到的最多现金数量。
 */
int f[N][2];
/**
 状态机 O(n)
把一个过程用一种确定的状态描述了出来
如 f[i][0] 表示没有偷第 i 个商店, f[i][1] 表示偷了第 i 个商店
则 f[i][0] 的入边（即过程）有两条 1. 偷了第 i - 1 个商店， 2. 没偷第 i - 1 个商店
而 f[i][1] 的入边仅有一条，即 没偷第 i - 1 个商店。
 */
//状态机解法
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        //初始化
        f[1][0] = 0, f[1][1] = a[1];
        //逐个把商店加入
        for (int i = 2; i <= n; i++) {
            //不偷i号商店,获利取原来前面i-1号商店决策完的最大值
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            //偷i号商店，获利取不偷i-1号商店的决策值，再加上当前商店的金额
            f[i][1] = f[i - 1][0] + a[i];
        }
        //最终的结果二选一
        printf("%d\n", max(f[n][0], f[n][1]));
    }
    return 0;
}