Codeforces 445A Boredom（DP+单调队列优化）

时间：2021-07-08 15:57:17

题目链接：http://codeforces.com/problemset/problem/455/A

题目大意：有n个数，每次可以选择删除一个值为x的数，然后值为x-1，x+1的数也都会被删除，你可以获得分值x，求出能获得的最大分值为多少。

解题思路：从小到大排序，去重一下, 用cnt[i]记录一下数字i出现次数。那么可以得到状态转移方程：dp[i]=max(dp[i],dp[j]+cnt[i]*a[i])（j<i&&a[i]-a[j]>1），再用单调队列优化一下就行了O(∩_∩)O~。

代码：

 #include<cstdio>

 #include<cmath>

 #include<cctype>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #include<set>

 #include<map>

 #include<stack>

 #include<string>

 #define INF 0x3f3f3f3f

 #define LC(a) (a<<1)

 #define RC(a) (a<<1|1)

 #define MID(a,b) ((a+b)>>1)

 #define fin(name)  freopen(name,"r",stdin)

 #define fout(name) freopen(name,"w",stdout)

 #define CLR(arr,val) memset(arr,val,sizeof(arr))

 #define FOR(i,start,end) for(int i=start;i<=end;i++)

 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

 using namespace std;

 typedef long long LL;

 const int N=5e6+;

 LL dp[N],cnt[N],q[N];

 int main(){

     FAST_IO;

     vector<int>v;

     int n,lim=;

     cin>>n;

     for(int i=;i<=n;i++){

         int x;

         cin>>x;

         v.push_back(x);

         cnt[x]++;

     }

     sort(v.begin(),v.end());

     v.erase(unique(v.begin(),v.end()),v.end());

     LL ans=,head=,tail=,cur=;

     q[tail++]=;

     for(int i=;i<v.size();i++){

         while(head<tail-&&q[head]<=q[head+]){

             head++;

         }

         dp[i]=q[head]+cnt[v[i]]*v[i];

         ans=max(dp[i],ans);

         while(cur<=i&&v[cur]<v[i+]-){

             LL t=dp[cur];

             while(head<tail&&q[tail-]<=t){

                 tail--;

             }

             q[tail++]=t;

             cur++;

         }

     }

     cout<<ans<<endl;

     return ;

 }

相关文章