大盗阿福

题目 大盗阿福

思路分析

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=1e5+10,INF=0x3f3f3f3f;
int n;
int w[N];
int f[N][2];//第i个店 状态 0 or 1

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T; cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++)   cin>>w[i];

        f[0][0]=0,f[0][1]=-INF;//第0家店被偷是不合法的 没被偷倒合理 属性max所以设置-inf
        for(int i=1;i<=n;i++){
            f[i][0]=max(f[i-1][1],f[i-1][0]);
            f[i][1]=f[i-1][0]+w[i];
        }
        cout<<max(f[n][0],f[n][1])<<endl;//因为不确定哪个大 还需要做个选择
    }

    return 0;
}

同类题型

视频讲解

⬅️ 状态机dp 🏠 00-冲刺国赛 ➡️ 股票买卖