題目描述

給定一個長度為?nn?的環(huán)狀數(shù)列?a1,a2,??,ana1?,a2?,?,an?，請從中間挑選出一些數(shù)字組成一個獨(dú)立集，使得該獨(dú)立集中的數(shù)字之和達(dá)到最大。

所謂環(huán)狀，是指在考慮相鄰關(guān)系時，需要把?a1a1??和?anan??也看做是一對鄰居。所謂獨(dú)立集，就是挑選出的數(shù)字在原來的圓環(huán)上不能相鄰。

輸入格式

• 第一行：單個整數(shù)表示?nn。
• 第二行：nn?個整數(shù)表示?a1,a2,??,ana1?,a2?,?,an?。

輸出格式

• 單個整數(shù)：表示獨(dú)立集的數(shù)字之和的最大值。

數(shù)據(jù)范圍

• 對于?30%30%?的數(shù)據(jù)，1≤n≤201≤n≤20；
• 對于?60%60%?的數(shù)據(jù)，1≤n≤50001≤n≤5000；
• 對于?100%100%?的數(shù)據(jù)，1≤n≤500,0001≤n≤500,000，
• 1≤ai≤1,000,0001≤ai?≤1,000,000。

樣例數(shù)據(jù)

輸入:

5
1 1 1 1 1

輸出:

2

輸入:

6
100 1 1 100 1 1

輸出:

200

說明:

這個例子告訴我們最優(yōu)獨(dú)立集不一定是最大獨(dú)立集

詳見代碼：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[500005];
long long dpq[500005];
long long dpb[500005];
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];if (i==1){dpq[i]=a[i];dpb[i]=0;}else{dpq[i]=max(dpq[i-1],dpq[i-2]+a[i]);dpb[i]=max(dpb[i-1],dpb[i-2]+a[i]);}}if (n==1) cout<<a[1];else cout<<max(dpb[n],dpq[n-1]);return 0;
}