【題目描述】

阿福是一名經(jīng)驗(yàn)豐富的大盜。趁著月黑風(fēng)高，阿福打算今晚洗劫一條街上的店鋪。

這條街上一共有 N 家店鋪，每家店中都有一些現(xiàn)金。阿福事先調(diào)查得知，只有當(dāng)他同時洗劫了兩家相鄰的店鋪時，街上的報警系統(tǒng)才會啟動，然后警察就會蜂擁而至。

作為一向謹(jǐn)慎作案的大盜，阿福不愿意冒著被警察追捕的風(fēng)險行竊。他想知道，在不驚動警察的情況下，他今晚最多可以得到多少現(xiàn)金？

【輸入】

輸入的第一行是一個整數(shù)T(T≤50) ，表示一共有T組數(shù)據(jù)。

接下來的每組數(shù)據(jù)，第一行是一個整數(shù)N(1≤N≤100,000) ，表示一共有N家店鋪。第二行是N個被空格分開的正整數(shù)，表示每一家店鋪中的現(xiàn)金數(shù)量。每家店鋪中的現(xiàn)金數(shù)量均不超過1000。

【輸出】

對于每組數(shù)據(jù)，輸出一行。該行包含一個整數(shù)，表示阿福在不驚動警察的情況下可以得到的現(xiàn)金數(shù)量。

【輸入樣例】

2
3
1 8 2
4
10 7 6 14

【輸出樣例】

8
24

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 100001 #define MOD 100001 #define E 1e-12 using namespace std; int a[N],f[N]; int main() {int t;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];f[0]=0;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; }

?

總結(jié)

以上是生活随笔為你收集整理的大盗阿福（信息学奥赛一本通-T1301）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。