$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

• $1. 状态表示$
  $集合：只从前\ i\ 个物品里面选，f[i][0]表示不选第\ i\ 个物品，f[i][1]表示选择第\ i\ 个物品$
  $属性：\max$

• $2. 状态转移$
  $不选第\ i\ 个物品：f[i][0]=\max(f[i-1][0],f[i-1][1])$
  $选择第\ i\ 个物品：f[i][1]=f[i-1][0]+w[i]$

可参考： 没有上司的舞会

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

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

int main()
{
    int T;
    cin>>T;

    while(T--)
    {
        cin>>n;

        for(int i=1;i<=n;i++) cin>>w[i];

        f[0][0]=f[0][1]=0;
        for(int i=1;i<=n;i++)
        {
            f[i][0]=max(f[i-1][0],f[i-1][1]); //不选第 i 个物品
            f[i][1]=f[i-1][0]+w[i]; //选择第 i 个物品
        }

        cout<<max(f[n][0],f[n][1])<<endl;
    }

    return 0;
}