1049 大盗阿福（状态机模型）

布满荆棘的人生 2022-08-28 13:57 116阅读 0赞

**1. 问题描述：**

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有 N 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？

**输入格式**

输入的第一行是一个整数 T，表示一共有 T 组数据。接下来的每组数据，第一行是一个整数 N ，表示一共有 N 家店铺。第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过1000。

**输出格式**

对于每组数据，输出一行。该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。

**数据范围**

1 ≤ T ≤ 50，  
1 ≤ N ≤ 10 ^ 5

**输入样例：**

2  
3  
1 8 2  
4  
10 7 6 14

**输出样例：**

8  
24

**样例解释**

对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。对于第二组样例，阿福选择第1和4家店铺行窃，获得的现金数量为10+14=24

来源：[https://www.acwing.com/problem/content/description/1051/][https_www.acwing.com_problem_content_description_1051]

**2. 思路分析：**

这道题目属于动态规划的经典题目，有两种常见的解决方法，第一种使用一般的动态规划思想解决，第二种使用**状态机模型**的分析思路解决。首先我们可以使用一般的动态规划思想求解，动态规划一般可以使用两个步骤分析，① 状态表示 ② 状态计算；根据题目的描述我们可以定义一个一维数组或者一维列表dp，其中dp\[i\]表示偷前i家店铺能够获得的最大现金；状态计算对应集合的划分，一般是找最后一个不同点（也即如何划分集合使得从前一个个状态转移到当前的状态），我们可以根据是否偷当前的第i家店铺划分为两个集合，划分完两个集合之后就可以清楚地得到状态转移方程为：dp\[i\] = max(dp\[i - 1\] + w\[i\]，dp\[i - 1\])

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_16_color_FFFFFF_t_70_g_se_x_16][]

第二种是根据状态机的思想来解决当前问题，状态机一个很重要的特点描述的是一个过程。我们要求当前的状态依赖于上一个状态而不依赖于上两个状态f\[i - 2\]，根据之前的想法当我们选择第i家店铺的时候不能够判断i - 1家店铺是否可以选择，所以我们需要将f\[i\]拆分为两个状态：f\[i\]\[0\]和f\[i\]\[1\]，f\[i\]\[0\]表示不偷第i个店铺，f\[i\]\[1\]表示选择偷第i个店铺（对应0和1两个状态），根据题目的描述可以得到状态机描述如下图所示，状态计算其实与状态机的描述是一一对应的，所以直接按照图中的状态描述编写代码即可。（状态机的本质就是将之前的状态细分从而使得状态之间的转换更加清晰）

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_16_color_FFFFFF_t_70_g_se_x_16 1][]

**3. 代码如下：**

**一般的思考方式：**

if __name__ == "__main__":
        T = int(input())
        while T > 0:
            n = int(input())
            a = list(map(int, input().split()))
            dp = [0] * (n + 1)
            dp[1] = a[0]
            for i in range(2, n + 1):
                # 对于当前的第i家店铺可以选也可以不选则偷盗这样可以对应两个状态转移
                dp[i] = max(dp[i - 1], dp[i - 2] + a[i - 1])
            print(dp[n])
            T -= 1

**状态机模型：**

if __name__ == '__main__':
        T = int(input())
        while T > 0:
            n = int(input())
            a = list(map(int, input().split()))
            INF = 10 ** 10
            dp = [[0] * 2 for i in range(n + 1)]
            dp[0][0] = 0
            dp[0][1] = -INF
            for i in range(1, n + 1):
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
                dp[i][1] = dp[i - 1][0] + a[i - 1]
            print(max(dp[n][0], dp[n][1]))
            T -= 1

[https_www.acwing.com_problem_content_description_1051]: https://www.acwing.com/problem/content/description/1051/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e0bfce16308948329d6beb6a871d4fa0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_16_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/3460e10d235e4b8289e5d6d0d6a2f2b1.png