题目链接

CodeForce 455A. Boredom

思路

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

记号

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

状态转移方程

对于a[i] > a[i-1] + 1，
那么当前选择不会影响到之前的点数。所以
dp[i][1]=max(dp[i−1][0],dp[i−1][1])+a[i]dp[i][1] = max(dp[i-1][0],dp[i-1][1]) + a[i]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]dp[i][1] = dp[j] + a[i]dp[i][1]=dp[j]+a[i]
2. 若此时不选择a[i]，那么当然得选择a[i-1]才会更好。故dp[i][0]=dp[i−1][1]dp[i][0]=dp[i-1][1]dp[i][0]=dp[i−1][1]
   对于a[i] == a[i-1]，那么当a[i-1]不能被选择时，a[i]也不能被选择。反之亦然。
   故有dp[i][0]=dp[i−1][0]dp[i][1]=dp[i−1][1]+a[i]dp[i][0]=dp[i-1][0] \\dp[i][1] = dp[i-1][1] + a[i] dp[i][0]=dp[i−1][0]dp[i][1]=dp[i−1][1]+a[i]

代码

#includeusing namespace std;typedef long long LL;
vector 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> dp(n + 1, vector(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]);
}