A48218. 大盗
填空题
较难
知识点
题目描述
大盗
题目描述
阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有 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 。
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
int f[N];
int main(){
int T,n,w;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&f[1]);
for(int i = 2;i <= n;i++){
scanf("%d",&w);
f[i] = max(f[i-1],f[i-2]+w);
}
printf("%d\n",f[n]);
}
return 0;
}
//方法2：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
int f[N][2];
int main(){
int T,n,w;
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;
}答案解析
作为一个典型的线性dp问题，本题可以用线性DP的解法来解决。状态表示f[i]表示在前i家店铺中能够获得的最多的现金。如果第i家店铺不洗劫，则获得的现金与在前i-1家店铺获得的最大现金一致，即f[i] = f[i-1]；如果第i家店铺洗劫，则第i-1家店铺不能洗劫，否则会触发报警器，故此时f[i] = f[i-2] + w，w表示洗劫第i家店铺可以获得的现金。故状态转移方程为f[i] = max(f[i-1],f[i-2]+w),i >= 2。这里的边界状态为f[0] = 0,f[1] = w1，因为只有一家商铺时选择洗劫必然是最优选择。
上一题
下一题