codeforces 260 div2 C题

时间:2022-05-09 19:39:41

C题就是个dp,把原数据排序去重之后得到新序列,设dp[i]表示在前i个数中取得最大分数,那么:

if(a[i] != a[i-1]+1)   dp[i] = cnt[a[i]]*a[i] + dp[i-1];

else      dp[i] = dp[i] = max(dp[i-1],a[i]*cnt[a[i]] + dp[i-2]),    dp[i-1]表示不取a[i], a[i]*cnt[a[i]] + dp[i-2]表示取a[i].

cnt[a[i]]是a[i]出现的次数。

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long int a[100010], dp[100010], cnt[100010];
int main(){
int n,num(0);
scanf("%d", &n);
for(int i = 0;i < n;i ++) cin >> a[i];
sort(a, a+n);
for(int i = 0;i < n;i ++) cnt[a[i]] ++;
for(int i = 1;i < n;i ++) if(a[i] != a[i-1]) a[++num] = a[i];
if(num == 0){
cout << a[0]*cnt[a[0]] << endl;
return 0;
}
dp[0] = a[0]*cnt[a[0]];
if(a[0] != a[1]-1) dp[1] = a[0]*cnt[a[0]] + a[1] * cnt[a[1]];
else dp[1] = max(cnt[a[0]] * a[0], cnt[a[1]] * a[1]);
for(int i = 2;i <= num;i ++){
if(a[i] != a[i-1] + 1) dp[i] = dp[i-1] + cnt[a[i]]*a[i];
else dp[i] = max(dp[i-1], a[i]*cnt[a[i]] + dp[i-2]);
}
cout << dp[num] << endl;
}