$\LARGE\color{orange}{刷题日记(算法提高课)}$

我们首先给出状态机的理解：用一系列确定的状态来表示一个过程

在这道题里面，从第一个店铺开始，直到最后一个店铺结束，这是一整个过程，我们可以用状态机来描述这个过程

首先对于每间店铺，都有偷和不偷两种选择，但这只是选择，并不是状态

「选择」这个动作会导致「状态」发生改变，用点来表示状态的话，那么选择就是两个点之间的一条有向边

我们用状态来描述就是，每一间店铺都有被偷和没被偷两种状态；被偷用 1 表示，没被偷用 0 表示

如果当前店铺被偷了，那么下一间店铺必须不能被偷，也就是只能从 1 转移到 0

如果当前店铺没有被偷，那么下一间店铺可以被偷也可以不被偷，即 0 可以转移到 0 也可以转移到 1

我们定义 $f[i][j]$ 表示的集合为：走了 $i$ 步，处于状态 $j$ 的所有走法，属性为所有走法当中价值的最大值

因此我们有：
$$ f[i][0]=max(f[i-1][0],f[i-1][1]),\ f[i][1]=f[i-1][0] $$

状态机有一个初始化的状态，即走了 0 步所处的状态，即我们初始化 $f[0][0]=0,\ f[0][1]=-\infty$

• 走 0 步处于状态 0 的走法为 0

• 走 0 步处于状态 1 的走法为负无穷

完整代码：

#include <iostream>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int f[N][2], w[N];
int n;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n;
        f[0][0] = 0, f[0][1] = -INF;
        for(int i = 1; i <= n; i++)
            cin >> w[i];
        for(int i = 1; i <= n; i++)
        {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + w[i];
        }
        cout << max(f[n][0], f[n][1]) << endl;
    }
    return 0;
}