前言

如果想看狀態(tài)機(jī)的詳解，點(diǎn)機(jī)這里:dp模型——狀態(tài)機(jī)模型C++詳解

1049. 大盜阿福

阿福是一名經(jīng)驗豐富的大盜。趁著月黑風(fēng)高，阿福打算今晚洗劫一條街上的店鋪。

這條街上一共有 N家店鋪，每家店中都有一些現(xiàn)金。

阿福事先調(diào)查得知，只有當(dāng)他同時洗劫了兩家相鄰的店鋪時，街上的報警系統(tǒng)才會啟動，然后警察就會蜂擁而至。

作為一向謹(jǐn)慎作案的大盜，阿福不愿意冒著被警察追捕的風(fēng)險行竊。

他想知道，在不驚動警察的情況下，他今晚最多可以得到多少現(xiàn)金？

輸入格式

輸入的第一行是一個整數(shù) T，表示一共有 T組數(shù)據(jù)。

接下來的每組數(shù)據(jù)，第一行是一個整數(shù) N，表示一共有 N家店鋪。

第二行是 N個被空格分開的正整數(shù)，表示每一家店鋪中的現(xiàn)金數(shù)量。

每家店鋪中的現(xiàn)金數(shù)量均不超過1000。

輸出格式

對于每組數(shù)據(jù)，輸出一行。

該行包含一個整數(shù)，表示阿福在不驚動警察的情況下可以得到的現(xiàn)金數(shù)量。

數(shù)據(jù)范圍

1≤T≤50，

1≤N≤1e5

輸入樣例：

2
3
1 8 2
4
10 7 6 14

輸出樣例：

8
24

樣例解釋

對于第一組樣例，阿福選擇第2家店鋪行竊，獲得的現(xiàn)金數(shù)量為8。

對于第二組樣例，阿福選擇第1和4家店鋪行竊，獲得的現(xiàn)金數(shù)量為10+14=24。

這道題的大意就是，有t組數(shù)據(jù)，每個有n個超市，告訴你每一家的價錢，不能盜竊相鄰的超市。

計算大盜能獲得的最大利益。

解題思路

這道題有兩種解法，第一種是普通的線性dp,第二種是狀態(tài)機(jī)dp。

第一種

用f[i]表示前i家商店阿?？梢垣@得的最大價值。

對于第i次選擇，只能選偷或者不偷，偷就是f[i - 2] + w[i]， 不偷就是f[i - 1]。

狀態(tài)轉(zhuǎn)移方程就是：

f[i] = max(f[i - 2] + w[i], f[i - 1]);

完整ac代碼如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 1e9;
int t, n;
int w[N], f[N];
int main() {scanf("%d", &t);while(t--) {scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &w[i]);memset(f, -INF, sizeof f);f[0] = 0;for(int i = 1; i <= n; i++) f[i] = max(f[i - 2] + w[i], f[i - 1]);printf("%d\n", f[n]);}return 0;
}

第二種就是今天講到的狀態(tài)機(jī)了，對于第i個超市，可以選擇偷或者不偷，我們用1表示偷，0表示不偷（都是當(dāng)前的超市）。

狀態(tài)轉(zhuǎn)移方程就是：

f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + w[i];

ac代碼如下：

#include <bits/stdc++.h>
using namespace std;
#define read(a) scanf("%d", &a);
const int N = 1e5 + 10, INF = 1e9;
int t, n;
int w[N], f[N][2];
int main() {read(t);while(t--) {read(n);for(int i = 1; i <= n; i++) read(w[i]);f[0][0] = 0, f[0][1] = -INF;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][1], f[n][0]));}return 0;
}