---
title: "大盗阿福"
created: 2025-11-28
tags:
  - 算法
---

# 大盗阿福

## 题目 [大盗阿福](https://www.acwing.com/problem/content/1051/)

![[image-5a6f3058.png]]

## 思路分析

![[image-9fe9eabf.png]]

## 代码实现

```cpp
#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|状态机dp]] 🏠 [[00-冲刺国赛]] ➡️ [[股票买卖|股票买卖]]