首页 > 代码库 > Codeforces Round #260 (Div. 2)C. Boredom

Codeforces Round #260 (Div. 2)C. Boredom

题意:N个数,我们可以选择某个数A,然后去掉A,和等于A+1,A-1的所有数字,得到A价值,问最后价值最大

思路:我们可以得到去掉A,得到的价值为A*A的个数,那么dp[i]=max(dp[i]+dp[i-2],dp[i-1]).记得开long long ,

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll a[100005];
 5 ll dp[100005];
 6 map<ll ,ll >mp;
 7 
 8 int main(){
 9     int n;
10     cin>>n;
11     for(int i=1;i<=n;i++){
12         scanf("%I64d",&a[i]);
13         mp[a[i]]++;
14     }
15     for(int i=1;i<=100000;i++)
16         dp[i]=mp[i]*i;
17     dp[0]=0;
18     for(int i=2;i<=100000;i++){
19         dp[i]=max(dp[i]+dp[i-2],dp[i-1]);
20     }
21     cout<<dp[100000]<<endl;
22 }

 

Codeforces Round #260 (Div. 2)C. Boredom