导言

状态机属于动态规划算法中,比较特殊的一类模型.

这种模型,可以抽象为图论增边模型,符合动态规划的有向无环图的概念.

题目精选

第一题

原题连接
算法分类:状态机分析+线性DP

此题也可以用闫式分析法.

题解连接

题目描述

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

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

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

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

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

输入格式

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

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

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

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

输出格式

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

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

数据范围

$1 \le T \le 50$,
$1 \le N \le 10^5$

输入样例：

2
3
1 8 2
4
10 7 6 14

输出样例：

8
24

样例解释

对于第一组样例，阿福选择第$2$家店铺行窃，获得的现金数量为$8$。

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

解题报告

题意理解

题目给定$n$个商铺,两个相邻的店铺不能同时打劫,要求打劫价值最高.

算法分析

所谓的状态机,可以默认为搜索的方向数组,加到了动态规划上面.(个人理解)

我们发现,这道题目一共就两种状态.

1. 不打劫
2. 打劫

既然状态已经罗列好了,接下来就是状态之间的转移.

①考虑,当前不打劫,能否转移到下一个不打劫.

可以的,因为这个商铺不打劫,那么下一个商铺当然也可以不打劫.

②考虑,当前不打劫,能否转移到下一个打劫.

可以的,因为这个商铺没有打劫,那么下一个商铺打劫,不违反相邻两个商铺不能都打劫.

③考虑,当前打劫,能否转移到下一个不打劫.

可以的,虽然当前商铺打劫,但是下一个商铺不打劫,所以满足题意.

④考虑,当前打劫,能否转移到下一个打劫.

不可以的 ,因为两个相邻的商铺不能同时都打劫.

Hint:对于状态机而言,如果上一个状态合法,而且可以转移到当前状态,那么这个转移合法.

个人理解:状态机的转移,就是图论中两个点连边,主要是判断这个转移是否合法,如果合法,就添加边.

状态转移方程

我们设$f[i][1]$表示选择当前商铺$i$的最优值.同理$f[i][0]$表示不选择当前商铺$i$最优值.

根据我们上面连好的边,不难推出.

当前不选
$f[i][0]=max(f[i-1][1],f[i-1][0])$

当前选择
$f[i][1]=max(f[i-1][0],max(f[i-2][1],f[i-2][0])+a[i])$

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+20;
int a[N],f[N][2],n,T;
inline void init()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(f,0,sizeof(f));
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        f[1][1]=a[1],f[1][0]=0;
        for(int i=2; i<=n; i++)
        {
            f[i][0]=max(f[i-1][0],f[i-1][1]);//上一次不选;上一次选;反正本次不选
            f[i][1]=max(f[i-1][0],max(f[i-2][1],f[i-2][0])+a[i]);//上一次不选,或者上一次总状态+选择本次
        }
        printf("%d\n",max(f[n][0],f[n][1]));
    }
}
signed main()
{
    init();
    return 0;
}