不相邻取数

难度：2星

设 $dp[i][0]dp[i][0]$ 为不取第 $ii$ 个数的情况下，前 $ii$ 个数不相邻取数的最大值；$dp[i][1]dp[i][1]$ 为取第 $ii$ 个数的情况下，前 $ii$ 个数不相邻取数的最大值。那么有转移方程：

不取当前数，那么前一个数取不取都行：

$dp[i][0]=max(dp[i-1][1],dp[i-1][0])dp[i][0]=max(dp[i-1][1],dp[i-1][0])$

若取当前数，那么前一个数一定不能取：

$dp[i][1]=dp[i-1][0]+a[i]dp[i][1]=dp[i-1][0]+a[i]$

最后需要输出 $max(dp[n][0],dp[n][1])max(dp[n][0],dp[n][1])$

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