首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。