zhi识点

1.当一个状态不好表示的时候，我们就可以用状态机的形式，把这个不好表示的状态分离开
2.状态压缩DP，就是我们不好直接用一个数来表示这一个状态，那么我们就用状态压缩的方式来表示这一个状态
3.初始化在状态机中被称为“入口”

写法1(思路图)

#include <bits/stdc++.h>
#define N 100100
using namespace std;

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

int main()
{
    cin >> t;
    while(t -- )
    {
        memset(f, 0, sizeof f);
        cin >> n;
        for(int i = 2; i <= n + 1; ++ i) cin >> w[i];

        for(int i = 2; i <= n + 1; ++ i)
            f[i] = max(f[i - 2] + w[i], f[i - 1]);

        cout << f[n + 1] << endl;
    }
}

写法2(见图)

#include <bits/stdc++.h>
#define N 100100
using namespace std;

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

int main()
{
    cin >> t;
    while(t -- )
    {
        memset(f, 0, sizeof f);
        cin >> n;
        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;
    }
}