思路分析

一：状态机：在dp的阶段表示中，如果前一个阶段的决策会影响到后面的阶段的决策，那么我们就可以才用状态机的形式来做，具体做法就是描述清楚当前的每一个决策(个人理解)

C++ 代码

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

int dp_0 = 0;
int dp_1 = 0;

int main(){
    int T;cin >> T;
    while(T -- ){
        int n;cin >> n;
        dp_0 = 0;
        dp_1 = 0;
        int x;
        for(int i = 1;i <= n;++i){
            cin >> x;
            int t1 = dp_0, t2 = dp_1;
            dp_0 = max(t1, t2);
            dp_1 = t1 + x;
        }
        cout << max(dp_0, dp_1) << endl;
    }

    return 0;
}