描述
亚历克斯不喜欢无聊。这就是为什么每当他感到无聊时，他都会想出一些游戏。一个漫长的冬夜，他想出了一个游戏。
给定由n个整数组成的序列a。玩家可以选择其中的整数。在一个步骤中，他可以选择序列中的一个元素（让我们把它表示为a[k]），然后删除它，此时a中所有值等于a[k]+ 1和a[k]- 1的元素也必须从序列中删除。这一步为玩家带来a[k]分数。
亚历克斯应该怎样选择，才能在游戏中得到的分数最多？
输入
输入一个t表示t个测试用例。
对于每个测试用例，输入一个整数n表示a中有n个整数。
接下来输入n个整数
输出
对于每个测试用例，输出一个整数表示可以得到的多分数。末行有换行
样例解析，有一个测试用例，包含7个整数的序列，选择3 5 7， 删除所有2,4，得到：
3×2+5+7=18
输入样例 1
1 7 5 3 4 2 3 7 2
输出样例 1
18
题解：
使用动态规划，map的作用是记录出现过的数以及出现的次数。DP[i]的意思是从0到i中，在数组中出现过的数能到达的最大的分数。
状态转移方程：
解释以下就是，要不选择前两个的最值加上自己，要不就不加自己之后的最大值。并且DP必须每个数都遍历过去，因为map只记录数值不记录数与数之间的关系。
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;
int t=0,n=0,i=0,j=0,num=0,maxn=0;
map<int ,int > mp;
map<int ,int >::iterator it;
ll dp[10001]={0};
main(){
cin >> t;
while(t>0){
mp.clear();
cin >> n;
maxn=0;
for(i=0;i<n;i++){
cin >> num;
if(num>maxn){
maxn=num;
}
mp[num]++;
}
dp[0]=0;
//cout << dp[0] << "\n";
dp[1]=mp[1];
//cout << dp[1] << "\n";
for(i=2;i<=maxn;i++){
dp[i]=max(dp[i-1],dp[i-2]+mp[i]*i);
}
cout << dp[maxn] << "\n";
t--;
}
}