Problem
给你 \(n\) 个数，如果你选了第 \(i\) 个数，就不能选第 \(i - 1\) 个数。
求最多选的数的和。
Solution
考虑 DP。
设 \(f_i\) 表示考虑到第 \(i\) 个数能获得的最大价值和。
即有如下状态转移方程式：
\[f_i = max\ ( f_{i - 1}, f_{i - 2} + a_i )
\]
其中，\(a_i\) 表示第 \(i\) 个数的值。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 5;
int T, n, a[N];
int f[N];
signed main() {
cin >> T;
for (int t = 1; t <= T; ++t) {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
f[1]=a[1];
for (int i = 2; i <= n; ++i)
f[i] = max (f[i - 1],
f[i - 2] + a[i]);
cout << "Case " << t << ": " << f[n] << '\n';
}
return 0;
}