题目描述
阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N
家店铺,每家店中都有一些现金。
阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。
作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。
他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?
样例
blablabla
算法1
用f[i]表示抢劫前i家店的最大利益。
每家店时都有两种选择:抢和不抢。并且不能抢连续的两家店。
不抢的话第i家的最大利益就等于第i-1家的最大利益:f[i]=f[i-1];
抢的话第i家的最大利益就等于第i-2家的最大利益再加上第i家店的价值:f[i]=f[i-2]
(状态机模型) $O(n)$
状态转移方程:
f[j]=max(f[j-1],f[j-2]+w)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N];
int t,n;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int w;
scanf("%d",&w);
f[1]=w;
for(int i=2;i<=n;i++){
int x;
scanf("%d",&x);
f[i]=max(f[i-1],f[i-2]+x);
}
cout<<f[n]<<endl;
}
return 0;
}