<—点个赞吧QwQ

宣传一下算法提高课整理

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 $N$ 家店铺，每家店中都有一些现金。

阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。

作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。

他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？

输入格式

输入的第一行是一个整数 $T$，表示一共有 $T$ 组数据。

接下来的每组数据，第一行是一个整数 $N$ ，表示一共有 $N$ 家店铺。

第二行是 $N$ 个被空格分开的正整数，表示每一家店铺中的现金数量。

每家店铺中的现金数量均不超过1000。

输出格式

对于每组数据，输出一行。

该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。

数据范围

$1 \le T \le 50$,
$1 \le N \le 10^5$

输入样例：

2
3
1 8 2
4
10 7 6 14

输出样例：

8
24

样例解释

对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。

对于第二组样例，阿福选择第1和4家店铺行窃，获得的现金数量为10+14=24。

思路1

闫氏$\text{DP}$分析法：
状态表示：$f_{i,k}$其中$k=0/1$

• 集合：抢劫前$i$家店，并且当前状态是$k$（$0$不偷，$1$偷）的所有抢劫方案
• 属性：$\max$

状态计算：

• 如果第$i$家店是要偷的，那么第$i-1$家店只能不偷，即$f_{i,1}=f_{i-1,0}+a_i$
• 如果第$i$家店是不偷的，那么第$i-1$家店偷不偷都可以，即$f_{i,0}=\max\lbrace f_{i-1,0},f_{i-1,1}\rbrace$

答案：

• 由于最后一家店偷不偷都可以，所以答案是$\max\lbrace f_{n,0},f_{n,1}\rbrace$

状态图：
来自一只野生彩色铅笔

代码1

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N];
int f[N][2];
int main () {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1;i <= n;i++) cin >> a[i];
        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] + a[i];
        }
        cout << max (f[n][0],f[n][1]) << endl;
    }
    return 0;
}

思路2

由于只用到前一列的数，所以可以用滚动数组优化。

代码2

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int a[N];
int f[2][2];
int main () {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1;i <= n;i++) cin >> a[i];
        memset (f,0,sizeof (f));
        for (int i = 1;i <= n;i++) {
            f[i & 1][0] = max (f[(i - 1) & 1][0],f[(i - 1) & 1][1]);
            f[i & 1][1] = f[(i - 1) & 1][0] + a[i];
        }
        cout << max (f[n & 1][0],f[n & 1][1]) << endl;
    }
    return 0;
}

思路3

闫氏$\text{DP}$分析法：
状态表示：$f_{i}$

• 集合：抢劫前$i$家店的所有方案
• 属性：$\max$

状态计算：

• 如果要抢劫第$i$家店，那么$i-1$家店就不能抢，即$f_{i-2}+a_i$
• 如果不抢劫第$i$家店，那么$i-1$家店能抢，即$f_{i-1}$
• 所以状态转移方程就是$f_i=\max\lbrace f_{i-1},f_{i-2}+a_i\rbrace$

答案：

• 根据定义 答案就是$f_n$

代码3

这应该是最短的了

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int a[N];
int f[N];
int main () {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1;i <= n;i++) cin >> a[i];
        f[1] = a[1];
        for (int i = 2;i <= n;i++) f[i] = max (f[i - 1],f[i - 2] + a[i]);
        cout << f[n] << endl;
    }
    return 0;
}