状态机模型

1.大盗阿福

原题链接

• 方法一 闫氏dp分析法

• 方法二 引入状态机模型

动态规划 O(n)

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

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

• 不打劫

• 打劫

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

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

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

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

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

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

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

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

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

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

个人理解:状态机的转移类似于图论里的添边，如果这条边合理，就引入这条边，状态机的选定类似于状态分类，走哪些种类的路达到最后的目的地

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1e5+10;
const int INF=0x3f3f3f3f;

int w[N],dp[N][2];
int n,t;

int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)   cin>>w[i];
        dp[0][0]=0,dp[0][1]=-INF;
        for(int i=1;i<=n;i++)
        {
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=dp[i-1][0]+w[i];
        }
        cout<<max(dp[n][0],dp[n][1])<<endl;
    }
    
    return 0;
}