【刷题】动态规划——状态机模型：大盗阿福_题解 不能选i和i+1 不能选i和i-k

题目链接

用背包的思路来考虑，f[i]表示选前i家店铺得到的现金最大。
有两种情况：1、选第i家店铺；2、不选第i家店铺
1、选了第i家店铺，不能选i-1家店铺：f[i] = f[i-2] + w[i]
2、不选第i家店铺，能选第i-1家店铺：f[i] = f[i-1]

#include <iostream>
using namespace std;
int t, n, w, f[100005];
int main() {
	scanf("%d", &t);
	while(t --) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i ++) {
			scanf("%d", &w);
			f[i] = max(f[i - 2] + w, f[i - 1]);
		}
		printf("%d\n", f[n]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这样做的坏处是依赖了上两层的状态，使用状态机模型可以只依赖i-1层的状态。

---

每家店铺有两种状态：1、被抢劫；2、没被抢劫

用0表示店铺i没被抢劫，1表示店铺i被抢劫。

对于i-1，考虑i。因为i-1没选，可以不选i（a），也可以选i（b）。
对于i-1，考虑i。因为i-1选了，所以只能不选i（c）。

f[i, j]表示走了i步，且位于状态j的走法获得金钱的最大值。

因此
对于f[i, 0]，有2条路径a和c可以抵达，f[i, 0]= max(f[i-1, 0], f[i-1, 1])
对于f[i, 1]，只有1条路径b可抵达，f[i, 1] = f[i-1, 0] + w[i]

#include <iostream>
using namespace std;
int t, n, w, f[100005][2];
int main() {
	scanf("%d", &t);
	while(t --) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i ++) {
			scanf("%d", &w);
			f[i][0] = max(f[i - 1][0], f[i - 1][1]);
			f[i][1] = f[i - 1][0] + w;
		}
		printf("%d\n", max(f[n][0], f[n][1]));
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16