描述
亚历克斯不喜欢无聊。这就是为什么每当他感到无聊时,他都会想出一些游戏。一个漫长的冬夜,他想出了一个游戏。
给定由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--;}
}