Codefroces455A Boredom

http://codeforces.com/problemset/problem/455/A

题意：选取一个数字AK，然后获得AK分数，序列中AK + 1 和 AK - 1的数字会被删除。然后重复，直到序列为空。

解法：好久没写过DP了，已经完全不会写了，即使这是一道超级基础的DP。

很明显，我们不知道选取哪个数字比较好，选取一个数字后有很明显的后效性，导致ak+1和ak-1也会受到影响。

解决后效性的最好办法就是DP，DP其实就是，先不看ak+1，一直专注于ak和小于ak的。我们就这样一直保证着ak之前的正确性，循环向后走，直到最后一个，前面都是正确的，那么最后一个也会是正确的且唯一。所以我们得到的公式就是 dp【i】 = max（dp【i-1】，dp【i】*i + dp【i-2】）。

代码如下：

#include<bits/stdc++.h> using namespace std; long long dp[100005]; int main() { int n, t; scanf("%d", &n); for(int i = 0; i < n; i++) { cin >> t; dp[t]++; } for(int i = 2; i < 100001; i++) dp[i] = max(dp[i - 1], dp[i] * i + dp[i - 2]); cout << dp[100000] << endl; return 0; }