CodeForce 455A. Boredom

题目链接

CodeForce 455A. Boredom

思路

因为跟序列的下标无关，所以先对数组a排个序。那么每次选择只会影响两侧的元素。

记号

令$dp[i]$表示排序后$a[\mathrm{1..}i]$能够获得的最大点数。
但是这样不足以区分是否当前元素可以被使用，所以再开一个维度，
令：
$dp[i][0]$表示我们无法使用当前元素$a[i]$所获得的最大点数。
$dp[i][1]$表示我们使用当前元素$a[i]$能够获得的最大点数。
那么对相邻的两个元素讨论即可。

状态转移方程

对于a[i] > a[i-1] + 1，
那么当前选择不会影响到之前的点数。所以
$$dp[i][1]=max(dp[i-1][0],dp[i-1][1])+a[i]$$
对于a[i] == a[i-1]+1，

1. 若此时选择a[i]，则与a[i-1]相等的都不能被选中。j是最大满足a[j] < a[i-1]的下标j，那么$dp[i][1]=dp[j]+a[i]$
2. 若此时不选择a[i]，那么当然得选择a[i-1]才会更好。故$dp[i][0]=dp[i-1][1]$
   对于a[i] == a[i-1]，那么当a[i-1]不能被选择时，a[i]也不能被选择。反之亦然。
   故有$$\begin{gathered} dp[i][0]=dp[i-1][0] \\ dp[i][1]=dp[i-1][1]+a[i] \end{gathered}$$

代码

#include<bits/stdc++.h>using namespace std;typedef long long LL;
vector<LL> a;int main() {int n;cin >> n;a.resize(n + 1);for (int i = 1; i <= n; ++i) {cin >> a[i];}sort(a.begin() + 1, a.end());vector<vector<LL>> dp(n + 1, vector<LL>(2));dp[1][1] = a[1];for (int i = 2; i <= n; ++i) {if (a[i] > a[i - 1] + 1) {// dp[i][1]表示使用了当前元素dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + a[i];} else {if (a[i] == a[i - 1] + 1) {// the prev of first element equal to a[i-1]int j = lower_bound(a.begin() + 1, a.begin() + i, a[i - 1]) - a.begin() - 1;dp[i][1] = max(dp[j][1], dp[j][0]) + a[i];dp[i][0] = dp[i - 1][1];} else if (a[i] == a[i - 1]) {dp[i][0] = dp[i - 1][0];dp[i][1] = dp[i - 1][1] + a[i];}}
//        printf("dp[%d]=%d\n", i, max(dp[i][0], dp[i][1]));}cout << max(dp[n][0], dp[n][1]);
}