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

柔光的暖阳◎ 2021-10-23 09:41 399阅读 0赞

题目链接：[http://codeforces.com/problemset/problem/455/A][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~。

代码：

1 #include<cstdio>
     2 #include<cmath>
     3 #include<cctype>
     4 #include<cstring>
     5 #include<iostream>
     6 #include<algorithm>
     7 #include<vector>
     8 #include<queue>
     9 #include<set>
    10 #include<map>
    11 #include<stack>
    12 #include<string>
    13 #define INF 0x3f3f3f3f
    14 #define LC(a) (a<<1)
    15 #define RC(a) (a<<1|1)
    16 #define MID(a,b) ((a+b)>>1)
    17 #define fin(name)  freopen(name,"r",stdin)
    18 #define fout(name) freopen(name,"w",stdout)
    19 #define CLR(arr,val) memset(arr,val,sizeof(arr))
    20 #define FOR(i,start,end) for(int i=start;i<=end;i++)
    21 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
    22 using namespace std;
    23 typedef long long LL;
    24 const int N=5e6+5;
    25 
    26 LL dp[N],cnt[N],q[N];
    27 
    28 int main(){
    29     FAST_IO;
    30     vector<int>v;
    31     int n,lim=0;
    32     cin>>n;
    33     for(int i=1;i<=n;i++){
    34         int x;
    35         cin>>x;
    36         v.push_back(x);
    37         cnt[x]++;
    38     }
    39     sort(v.begin(),v.end());
    40     v.erase(unique(v.begin(),v.end()),v.end());
    41     LL ans=0,head=0,tail=0,cur=0;
    42     q[tail++]=0;
    43     for(int i=0;i<v.size();i++){
    44         while(head<tail-1&&q[head]<=q[head+1]){
    45             head++;
    46         }
    47         dp[i]=q[head]+cnt[v[i]]*v[i];
    48         ans=max(dp[i],ans);
    49         while(cur<=i&&v[cur]<v[i+1]-1){
    50             LL t=dp[cur];
    51             while(head<tail&&q[tail-1]<=t){
    52                 tail--;
    53             }
    54             q[tail++]=t;
    55             cur++;
    56         }
    57     }
    58     cout<<ans<<endl;
    59     return 0;
    60 }

转载于:https://www.cnblogs.com/fu3638/p/8034377.html

[http_codeforces.com_problemset_problem_455_A]: http://codeforces.com/problemset/problem/455/A