AcWing 1049. 大盗阿福 状态机模型dp

//f[i,j]表示所有走了i步，且当前位于状态j的所有走法   j=1表示选第i个  j=0表示不选 
//如果j=0 那么表示不选第i个 那么就可以从f[i-1,0]和f[i-1,1]转移过来
//如果j=1 那么表示选第i个，那么就可以f[i-1,0]+w[i]转移过来 

//入口 可以思考一下 
//初始的时候 是位于状态0的  
//左边可以来一个虚拟的边界，虚拟边界时不存在的，所以一定不能选
//所以入口指向0，不能指向1 
//所以初始化的时候 f[0,0]=0,f[0,1]=负无穷 
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int w[N], f[N][2];
int main() {
    int T;
    scanf("%d", &T);
    while (T -- ) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &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];
        }
        printf("%d
", max(f[n][0], f[n][1]));
    }
    return 0;
}