题解 | #小彩的数组选数#

没有题解，浅浅发一篇吧。

看一眼，有点像dp，再看一眼，确实是dp。虽然，选中一个数会使得前后都变成零，但考虑dp为前 个长度的得分最大值即可，只要考虑前一个数和当前数 的比较，不会违背无后效性。即：

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    int a[n+1];
    for(int i=1;i<=n;i++) cin >> a[i];
    int dp[n+1];
    dp[0] = 0;
    dp[1] = a[1];
    for(int i=2;i<=n;i++){
        dp[i] = max(dp[i-1],dp[i-2]+a[i]);
    }
    cout << dp[n];
}