經(jīng)驗(yàn)值：1200

時(shí)間限制：1000毫秒

內(nèi)存限制：128MB

合肥市第34屆信息學(xué)競(jìng)賽（2017年）

?不許抄襲，一旦發(fā)現(xiàn)，直接清空經(jīng)驗(yàn)！

題目描述 Description

卡卡西和小朋友們做完了燒腦的數(shù)字游戲，決定放松一下，他們來(lái)到萬(wàn)達(dá)樂(lè)園，樂(lè)園中有很多的游玩項(xiàng)目，每玩一個(gè)項(xiàng)目就能獲取一定的體驗(yàn)積分，不同的項(xiàng)目產(chǎn)生不同體驗(yàn)積分，假設(shè)樂(lè)園所有游樂(lè)項(xiàng)目正好排成一排，并且游客們不能游玩任意相鄰兩個(gè)項(xiàng)目，那么卡卡西如何挑選游玩項(xiàng)目，使得這次萬(wàn)達(dá)行他能獲得最多的體驗(yàn)積分值呢。

輸入描述 Input Description

輸入 共兩行， 第一行是個(gè)正整數(shù) n，表示萬(wàn)達(dá)樂(lè)園的游項(xiàng)目數(shù) 。

第 二行是 n個(gè)用空格隔開(kāi)的正整數(shù) ，分別表示每個(gè)游樂(lè)項(xiàng)目的體驗(yàn)積值 。

輸出描述 Output Description

輸出只有一個(gè)正整數(shù)，為最多的體驗(yàn)積分值。

樣例輸入 Sample Input

輸入樣例1： 5 3 10 8 20 21 輸入樣例2： 5 3 17 8 20 21

樣例輸出 Sample Output

輸出樣例1： 32 輸出樣例2： 38

數(shù)據(jù)范圍及提示 Data Size & Hint

樣例1說(shuō)明：
一共 5個(gè)游玩項(xiàng)目，卡卡西選擇第一、三和第五個(gè)游玩，可獲得 3+8+21=32的體驗(yàn)積分值。

樣例2說(shuō)明：
一共 5個(gè)游玩項(xiàng)目，卡卡西選擇第二和第五個(gè)游玩，可獲得17+21=38的體驗(yàn)積分值。

數(shù)據(jù)范圍 :
5≤n≤1000 ；
1≤每個(gè)游玩項(xiàng)目體驗(yàn)積分值≤500

#include<bits/stdc++.h>
using namespace std;
int n,dp[1005],x[1005];
int main(){
cin>>n;
for(int i=1;i<=n;i++){cin>>x[i];
}
dp[1]=x[1];
for(int i=2;i<=n;i++){dp[i]=max(dp[i-2]+x[i],dp[i-1]);
}
cout<<dp[n];
return 0;
}