题意：N个数，我们可以选择某个数A，然后去掉A，和等于A+1，A-1的所有数字，得到A价值，问最后价值最大
思路：我们可以得到去掉A，得到的价值为A*A的个数，那么dp[i]=max(dp[i]+dp[i-2],dp[i-1]).记得开long long ,
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll a[100005]; 5 ll dp[100005]; 6 map<ll ,ll >mp; 7 8 int main(){ 9 int n; 10 cin>>n; 11 for(int i=1;i<=n;i++){ 12 scanf("%I64d",&a[i]); 13 mp[a[i]]++; 14 } 15 for(int i=1;i<=100000;i++) 16 dp[i]=mp[i]*i; 17 dp[0]=0; 18 for(int i=2;i<=100000;i++){ 19 dp[i]=max(dp[i]+dp[i-2],dp[i-1]); 20 } 21 cout<<dp[100000]<<endl; 22 }
Codeforces Round #260 (Div. 2)C. Boredom
原文：http://www.cnblogs.com/hhxj/p/7101953.html