1301：大盗阿福

经典的dp打家劫舍问题

状态设计

dp[i][0]：在前i个店铺中选，且不选第i家的最大和

dp[i][1]：在前i个店铺中选，且选第i家的最大和

状态转移

• dp[i][0] = max(dp[i-1][1], dp[i-1][0];

第i家店不选，那么我们可以选第i-1个店 也可以不选（第i-1个店）

• dp[i][1] = dp[i-1][0] + a[i];

第i家店选，那么我们第i-1个店一定不能选（因为不能选相邻两个），还要记得加上第i家店的价值

初始化

dp[1][0] = 0

dp[1][1] = a[1]

（不懂得化可以再看一下 ⌈状态设计⌋ ）

答案

max(dp[n][0], dp[n][1])

代码

//大盗阿福
#include <iostream>
#include <cstring>using namespace std;const int N = 100010;
int a[N], dp[N][1];int main() {int t;scanf ("%d", &t);while (t --) {/*状态设计dp[i][0/1] : 打劫前i个店铺可得的最大金额, 且不包含/包含第i个数字的最大值状态转移dp[i][0] = max(dp[i-1][1], dp[i-1][0]);dp[i][1] = dp[i-1][0] + a[i];初始化dp[1][1] = a[1];输出max(dp[n][0], dp[n][1]);*/int n;scanf ("%d", &n);for (int i = 1; i <= n; i ++)scanf ("%d", &a[i]);dp[1][1] = a[1];for (int i = 2; i <= n; i ++)dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]), dp[i][1] = dp[i - 1][0] + a[i];printf ("%d\n", max(dp[n][0], dp[n][1]));}return 0;
}
/*
【输入样例】
2
3
1 8 2
4
10 7 6 14
【输出样例】
8
24
*/

原题链接：

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)