欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CF1082E Increasing Frequency

程序员文章站 2024-03-19 09:38:22
...

题意
给你一个长度为n的数列a,你可以任意选择一个区间[L,R]并给区间每个数加上一个整数k,求这样一次操作后数列中最多有多少个数等于c。

写法比较巧妙的一个贪心题。

显然可以想到相同的数字要放在一起来维护。

具体可以对每种数字开一个vector。然后枚举左端点,此时右端点的贡献是一个只与右端点下标有关的式子。
差不多长这个样子

(id[r]-id[l-1])-(s[r]-s[l-1])

显然可以用线段树来维护。

以上是自闭青年的做法。

考虑文艺青年会怎么做:

既然一个区间的贡献可以直接计算,那么就直接O(n)扫描一遍,用dp数组记录当前每一种数字可以取到的价值最大的前缀。

枚举到第i位时,显然可以对dp[a[i]]做一个更新。

dp[a[i]]=max(dp[a[i]],s[i-1])+1;

然后,对每个时刻进行答案更新即可。ans=max(ans,dp[i]+s[n]-s[i]);

#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#define N 1100000
#define L 1000000
#define eps 1e-7
#define inf 1e9+7
#define ll long long
using namespace std;
inline int read()
{
    char ch=0;
    int x=0,flag=1;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*flag;
}
int a[N],s[N],dp[N];
int main()
{
    int n=read(),k=read(),ans=0;
    for(int i=1;i<=n;i++)a[i]=read(),s[i]=s[i-1]+(a[i]==k);
    for(int i=1;i<=n;i++)
    {
        dp[a[i]]=max(dp[a[i]],s[i-1])+1;
        ans=max(ans,dp[a[i]]+s[n]-s[i]);
    }
    printf("%d",max(ans,s[n]));
    return 0;
}