5.2 KiB
一、题目描述
阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺，每家店中都有一些现金。
阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。
他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？
输入格式
输入的第一行是一个整数 T，表示一共有 T 组数据。
接下来的每组数据，第一行是一个整数 N ，表示一共有 N 家店铺。
第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。
每家店铺中的现金数量均不超过1000。
输出格式 对于每组数据，输出一行。
该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。
数据范围
1≤T≤50,1≤N≤10^5
输入样例：
2
3
1 8 2
4
10 7 6 14
输出样例：
8
24
样例解释
对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。
对于第二组样例，阿福选择第1和4家店铺行窃，获得的现金数量为10+14=24。
二、状态机解法
我们把f数组定为二维的，即f[i][j]
我们用数组储存两种情况：偷与不偷。
f[i][0] 代表的是不偷第i家店铺能得到的最多现金数量；
f[i][1] 代表的是偷第i家店铺能得到的最多现金数量。
则就会出现三种情况：
解释：
图中红色的线是可行方案，你可以不抢第i−1家，也不抢第i家；
你可以不抢第i−1家，但抢第i家。
你可以抢第i−1家，但不抢第i家；
那么我们就可以得出状态转移方程了：
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + w[i];
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int T; //T组数据
int n; //每一组数据的个数n
int a[N]; //每个商店的金钱数量
/**
f[i][0] 代表的是不偷第i家店铺能得到的最多现金数量；
f[i][1] 代表的是偷第i家店铺能得到的最多现金数量。
*/
int f[N][2];
/**
状态机 O(n)
把一个过程用一种确定的状态描述了出来
如 f[i][0] 表示没有偷第 i 个商店, f[i][1] 表示偷了第 i 个商店
则 f[i][0] 的入边（即过程）有两条 1. 偷了第 i - 1 个商店， 2. 没偷第 i - 1 个商店
而 f[i][1] 的入边仅有一条，即 没偷第 i - 1 个商店。
*/
//状态机解法
int main() {
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][0] = 0, f[1][1] = a[1];
//逐个把商店加入
for (int i = 2; i <= n; i++) {
//不偷i号商店,获利取原来前面i-1号商店决策完的最大值
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
//偷i号商店，获利取不偷i-1号商店的决策值，再加上当前商店的金额
f[i][1] = f[i - 1][0] + a[i];
}
//最终的结果二选一
printf("%d\n", max(f[n][0], f[n][1]));
}
return 0;
}
三、线性DP解法
我们可以定义一个数组，为f[i]。
f[i] 表示抢劫前i家能得到的最多现金数量。
那么我们前i家的抢劫结果就有两种情况：
第一种情况：不偷第i家店铺
那么f[i]=f[i−1];
第二种情况：偷第i家店铺
那么f[i]=f[i−2]+w[i]
(w[i] 表示第i家店铺总共的现金)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int f[N];//DP数组，抢前i个店铺可以获取到的最大价值是多少
int a[N];//抢劫第i个店铺可以获取到的利益w[i]
//线性DP解法
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
//base case
f[0] = 0; //还没开始抢，那么利益必须是0
f[1] = a[1]; //抢了第一个，只能是利益为w[1]
//从第二个开始，有递推关系存在,以抢与不抢第i个为理由进行分类
for (int i = 2; i <= n; i++)
//f[i-1]表示不抢第i个，那么利益就是f[i-1]
//如果抢了第i个，那么获取到w[i]的利益，同时，前面的只能依赖于f[i-2]
//max表示决策，到底抢两个中的哪个合适呢？
f[i] = max(f[i - 1], f[i - 2] + a[i]);
//输出结果
printf("%d\n", f[n]);
}
return 0;
}