桂林电子科技大学第三届ACM程序设计竞赛 I题

链接：https://ac.nowcoder.com/acm/contest/558/I
来源：牛客网

小猫在研究序列。小猫在研究选择。
给定一个长度为N的序列a1,a2,…,aN，请你在这N个元素中选出一些（可以不选，可以全选），使得对于任意1≤i<N，ai与ai+1不被同时选，求选出的数的和最大是多少。
思路：dp水题 dp[i] = max(dp[i - 1], dp[i - 2] + a[i])

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;
int dp[maxn], a[maxn];
int main() {
    int T, n;
    cin >> T;
    while (T--) {
        memset(dp, 0, sizeof(dp));
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        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] << endl;
    }
    return 0;
}