题目链接：http://www.codeforces.com/problemset/problem/455/A
题意：给定n个数，每次拿出一个数，获得这个数值的分数，并删去比这个数大1和比这个数小1的所有数字，求最大分数。其中 1≤n≤105 ， 1≤ai≤105 。
想法：一开始在思考是不是有最大的策略，后来发现直接dp即可。我们记录下每个数字出现的次数h[i]，然后我们设dp[i]为考虑到数字i时得到的最大分数，那么显然dp[i] = max(dp[i - 1], dp[i - 2] + h[i] * i)，我们从最小的数字遍历到最大的数字即可。trick：第一次WA因为爆了Int。
代码如下：
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> typedef long long ll; const int MAXN = 100000 + 10; int h[MAXN]; ll dp[MAXN]; int main(){ int n; scanf("%d", &n); int ma = -1; for(int i = 0; i < n; ++i){ int x; scanf("%d", &x); ++h[x]; ma = std::max(ma, x); } memset(dp, 0, sizeof(dp)); dp[1] = h[1]; for(int i = 2; i <= ma; ++i){ dp[i] = std::max(dp[i - 1], dp[i - 2] + 1LL * h[i] * i);//可能会爆int } std::cout << dp[ma] << std::endl; return 0; }