抢分制C++

抢分制
比赛题目  题目统计 全部提交 时间限制：C/C++ 1000MS，其他语言 2000MS
内存限制：C/C++ 256MB，其他语言 512MB

描述

 

xiaoliu在玩一个抢分制的游戏，这个游戏规则如下：
先给1个含n个正整数的数组a，每次xiaoliu可以选择删除一个数a[i]，将数组中的等于a[i]+1和a[i]-1的元素都删除并且xiaoliu获得a[i]分。
xiaoliu想问你他能得的最高分是多少。

 

输入描述

 

第一行一个整数n(0<n<=100000);
第二行n个数ai(0<ai<=10000)。

 

输出描述

 

一个整数代表xiaoliu能获得的最高分。

 

用例输入 1 

3 3 4 2

用例输出 1 

6

用例输入 2 

5 1 2 2 2 3

用例输出 2 

6

提示

 

同一个数可以多次出现多次删除。

 

 

题目：

其a[i]的范围只有1e4，所以可以直接从1枚举到1e4每一次取删除这个数或者不删这个数的最大得分情况，如果删了这个数那么他的得分就是当前数-2+当前数*它的数量的情况得到不删就是当前数-1，两种取最大值。

然后我们就可以遍历数组知道：dp[i]=max(dp[i-1],dp[i-2]+i*bb[i]);

就是动态规划的思想：
AC：

#include<bits/stdc++.h> using namespace std; const int N=1e4+10;  int main(){     int n;     cin>>n;     int aa[n];     for(int i=0;i<n;i++)cin>>aa[i];     sort(aa,aa+n);     int temp=1,index=0,bb[N]={0},dp[N]={0};     for(int i=0;i<n;i++)         if(aa[i]!=aa[i+1]){             bb[aa[i]]=temp;             temp=1;         }         else temp++;     int ans=0;     for(int i=1;i<=10000;i++){         dp[i]=max(dp[i-1],dp[i-2]+i*bb[i]);         ans=max(dp[i],ans);     }     cout<<ans<<endl;     return 0; }