闫式dp分析

状态表示:

f[0][i] 表示不选第i个物品的最优解
f[1][i] 表示选取第i个物品的最优解

状态转移方程:

f[0][i] = max(f[0][i - 1], f[1][i - 1]);
f[1][i] = f[0][i-1] + w[i];

C++代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int res[2][N];
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];

        memset(res, 0, sizeof(res));

        for(int i = 1; i <= n; i++)
        {
            res[0][i] = max(res[0][i - 1], res[1][i - 1]);
            res[1][i] = res[0][i - 1] + a[i];
        }
        cout << max(res[0][n], res[1][n]) << endl;
    }

    return 0;   
}