题解 | 不相邻取数

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    vector<vector<int>> dp(n,vector(2,0));
    dp[0][0]=0;
    dp[0][1]=arr[0];
    for(int i=1;i<n;i++){
        dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
        dp[i][1]=dp[i-1][0]+arr[i];
    }
    cout<<max(dp[n-1][0],dp[n-1][1]);
    return 0;
}
// 64 位输出请用 printf("%lld")