计蒜客 - T1227 大盗阿福

本文主要是介绍计蒜客 - T1227 大盗阿福，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

计蒜客 - T1227 大盗阿福

原题链接

思路

动态规划问题，dp[i]表示1~i家店铺抢劫可以获得的现金数的最大值，状态方程dp[i]=max(dp[i-1],dp[i-2]+a[i]);。划分第i家选与不选的情况，如果不选第i家，那么最大值就是dp[i-1]，如果选第i家，因为是不能选相邻两家，那么最大值就是dp[i-2]+a[i]，然后找到这两者的最大值。代码很简单，如下。

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

这篇关于计蒜客 - T1227 大盗阿福的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---