1.大盜阿福

原題鏈接

• 方法一 閆氏dp分析法

• 方法二 引入狀態(tài)機(jī)模型

動(dòng)態(tài)規(guī)劃 O(n)

所謂的狀態(tài)機(jī),可以默認(rèn)為搜索的方向數(shù)組,加到了動(dòng)態(tài)規(guī)劃上面.(個(gè)人理解)

我們發(fā)現(xiàn),這道題目一共就兩種狀態(tài).

• 不打劫

• 打劫

既然狀態(tài)已經(jīng)羅列好了,接下來(lái)就是狀態(tài)之間的轉(zhuǎn)移.

①考慮,當(dāng)前不打劫,能否轉(zhuǎn)移到下一個(gè)不打劫.

可以,因?yàn)檫@個(gè)商鋪不打劫,那么下一個(gè)商鋪當(dāng)然也可以不打劫.

②考慮,當(dāng)前不打劫,能否轉(zhuǎn)移到下一個(gè)打劫.

可以,因?yàn)檫@個(gè)商鋪沒(méi)有打劫,那么下一個(gè)商鋪打劫,不違反相鄰兩個(gè)商鋪不能都打劫.

③考慮,當(dāng)前打劫,能否轉(zhuǎn)移到下一個(gè)不打劫.

可以,雖然當(dāng)前商鋪打劫,但是下一個(gè)商鋪不打劫,所以滿足題意.

④考慮,當(dāng)前打劫,能否轉(zhuǎn)移到下一個(gè)打劫.

不可以 ,因?yàn)閮蓚€(gè)相鄰的商鋪不能同時(shí)都打劫.

對(duì)于狀態(tài)機(jī)而言,如果上一個(gè)狀態(tài)合法,而且可以轉(zhuǎn)移到當(dāng)前狀態(tài),那么這個(gè)轉(zhuǎn)移合法.

個(gè)人理解:狀態(tài)機(jī)的轉(zhuǎn)移類似于圖論里的添邊，如果這條邊合理，就引入這條邊，狀態(tài)機(jī)的選定類似于狀態(tài)分類，走哪些種類的路達(dá)到最后的目的地

#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;
}