AcWing 1049. 大盗阿福【动态规划(状态机) 】题解

浅浅的花香味﹌ 2021-07-25 02:58 465阅读 0赞

### 1.题目 ###

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 N 家店铺，每家店中都有一些现金。

阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。

作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。

他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？

**输入格式**  
输入的第一行是一个整数 T，表示一共有 T 组数据。

接下来的每组数据，第一行是一个整数 N ，表示一共有 N 家店铺。

第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。

每家店铺中的现金数量均不超过1000。

**输出格式**  
对于每组数据，输出一行。

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

**数据范围**  
1≤T≤50,  
1≤N≤105  
**输入样例：**  
2  
3  
1 8 2  
4  
10 7 6 14  
**输出样例：**  
8  
24  
**样例解释**  
对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。

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

### 2.思路 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center 1]  
**状态表示：**  
我们设`f[i][1]`表示选择当前商铺i的最优值，同理`f[i][0]`表示不选择当前商铺i的最优值。  
对于`f[i][0]`:  
不抢第 `i` 个店铺可以由不抢第`i-1`个商店，或者抢第`i-1`个商店转移过来。  
**转移方程为：**  
`f[i][0]=max(f[i-1][0],f[i-1][1])`  
对于`f[i][1]`:  
由于不能抢相邻的，所以抢第`i`个店铺时一定不能抢第`i−1`个店铺，因此抢劫第`i`个商店只能从不抢第`i-1`个店转移过来。  
`f[i][1]=f[i-1][0]+w[i]`

### 3.代码 ###

/* 状态机模型 */
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int N=1e5+10,INF=1e9;
    int w[N],f[N][2];
    int main()
    { 
        int T;
        scanf("%d",&T);
        while(T--)
        { 
            int n;
            scanf("%d",&n);
            f[0][0]=0,f[0][1]=-INF;  //初始化
            for(int i=1;i<=n;i++) scanf("%d",&w[i]);
            for(int i=1;i<=n;i++)
            { 
                f[i][0]=max(f[i-1][0],f[i-1][1]);
                f[i][1]=f[i-1][0]+w[i];
            }
            printf("%d\n",max(f[n][0],f[n][1]));
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20210724/ed35c0a81fd84ec0b7bfcf66a9bd03b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210724/b0a0867045db4538966a57350f38da03.png