今天早上找一道题的bug，还是找不出来，下午刷了几道水题，晚上准备回家的事，
然后本来想打CF的，一看，数学场，不打了。
这道题的题意：
给出一个序列，每次你可以从这个序列里面选择一个数ak，删除，然后你的得分+ak，
代价是序列里面值为ak+1,ak-1的元素都删除
问：你能得到的最大得分是多少
思路：
你若删除了一个值为a的数，你的得分就是a*序列里面a的个数
因为a+1和a-1都被删除了，则其余的a不会被a+1,a-1这种情况删除了，你一定可以得到所有a的分数
所以这道题就是：在序列里面选择一些数值，你的得分+数值*该值出现的个数，并且，
数值+1和数值-1的数你就不能选了。
num[i]表示值i出现的次数。
_max表示出现的最大的值
dp[i][0]:表示从值1选择到i，如果不选择值i，可以得到的最大分数
dp[i][1]:表示从值1选择到值i，如果选择了值i，可以得到的最大分数。
注意：
1.这道题最后的结果要long long
2.小心中间过程溢出，我就是这个贡献了2个wa
3.CF的long long 要用cout输出
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 5 using namespace std; 6 #define LL long long 7 const int maxn=1e5+10; 8 9 inline LL max(LL x,LL y) 10 { 11 return x>y?x:y; 12 } 13 14 int a[maxn]; 15 LL dp[maxn][2]; 16 17 int main() 18 { 19 int n; 20 scanf("%d",&n); 21 int _max=-1; 22 memset(a,0,sizeof a); 23 for(int i=1;i<=n;i++) 24 { 25 int u; 26 scanf("%d",&u); 27 a[u]++; 28 if(u>_max) 29 _max=u; 30 } 31 32 memset(dp,0,sizeof dp); 33 for(int i=1;i<=_max;i++) 34 { 35 dp[i][1]=dp[i-1][0]+(LL)a[i]*i; 36 dp[i][0]=max(dp[i-1][1],dp[i-1][0]); 37 } 38 39 cout<<max(dp[_max][1],dp[_max][0])<<endl; 40 41 return 0; 42 }
原文：http://www.cnblogs.com/-maybe/p/4719861.html
