CodeForces - 1082E
E. Increasing Frequency
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given array aa of length nn. You can choose one segment [l,r][l,r] (1≤l≤r≤n1≤l≤r≤n) and integer value kk (positive, negative or even zero) and change al,al+1,…,aral,al+1,…,ar by kk each (i.e. ai:=ai+kai:=ai+k for each l≤i≤rl≤i≤r).
What is the maximum possible number of elements with value cc that can be obtained after one such operation?
Input
The first line contains two integers nn and cc (1≤n≤5?1051≤n≤5?105, 1≤c≤5?1051≤c≤5?105) — the length of array and the value cc to obtain.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤5?1051≤ai≤5?105) — array aa.
Output
Print one integer — the maximum possible number of elements with value cc which can be obtained after performing operation described above.
Examples
input
Copy
6 9
9 9 9 9 9 9
output
Copy
6
input
Copy
3 2
6 2 6
output
Copy
2
Note
In the first example we can choose any segment and k=0k=0. The array will stay same.
In the second example we can choose segment [1,3][1,3] and k=?4k=?4. The array will become [2,?2,2][2,?2,2].
分析：
参考大佬思路：https://blog.csdn.net/LSD20164388/article/details/84697742
题意：
给你两个数n和c，n表示有长度的序列，你可以使任意一段区间加上任意数k，使整个序列c出现最多次数
分析：
首先，可以分析出，最大数量可能分两部分，一部分原本序列且未改变c的数量，另一个部分你改变区间后的序列含c的数量。
然后，我们发现如果我们改变[l,r]区间，那么1-l-1含c的数量，和r+1—n含c的数量就确定了，关键是中间的数量，最大出现的数的个数如何求。
其实到这里，就是做出这题的关键了，第一中间数不好求，暴力肯定超时，关键，那一个最大出现相同数如何求，dp就要登场了。
这时候就要改变思路了，我们这样求，
我们不是难以求(l,r)之间相同的数吗，我们开一个数组pre[i]=x:：表示对于某个数 a[i]==x，上一次出现的位置是 j，即：a[j]=a[i]=x
我们来看一下下面这个图
Ok，我们先定义一下DP：
dp[i]表示从1到i可以出现的最大c的数量，分两种情况max(a[i]第一次出现的位置和当前位置内的a[i]变成c的数量+前pos-1个不改变最大的含c的数量, 前i-1个不改变最大的含c的数量+改变a[i]到c的数量)。
这里需要解释一下下面动态规划方程如何实现的：因为这是一个从前往后推的一个过程，第一次出现a[i]的dp[i]会保存到第二次a[i]出现的当中，就这么一直推下去，所以如果前面有好多a[i],只要找到最近的a[i],即pre[a[i]]=pos即可，
up[i]表示从第一个位置到当前位置i时c出现的次数。
down[i]表示从最后一个位置到当前位置i时c出现的次数。
状态转移方程：
dp[i]=max(up[i-1]+1,dp[pre[a[i]]]+1);
pre[i]=i;
ans=max(ans,dp[i]+down[i+1]);
初始化：
DP[1]=max(up[0]+1，dp[pre[a[1]]]+1)
即DP[1]=1
#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;#define rep(i,n) for(int i=0;i<n;i++)
#define sd(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define pd(n) scanf("%d\n",n)
#define pll(n) scanf("%lld\n",n)
#define MAX 26
const int N=5e5+10;
typedef long long ll;
const ll mod=1e9+7;
ll n,c;
ll a[N],pre[N],up[N],down[N],dp[N];
int main()
{scanf("%lld%lld",&n,&c);for(int i=1;i<=n;i++){scanf("%d",&a[i]);up[i]=up[i-1]+(a[i]==c);}for(int i=n;i>=1;i--){down[i]=down[i+1]+(a[i]==c);}ll ans=0;for(int i=1;i<=n;i++){dp[i]=max(up[i-1]+1,dp[pre[a[i]]]+1);//cout<<up[i-1]<<" "<<pre[a[i]]<<" "<<endl;// cout<<i<<" "<<a[i]<<" "<<dp[i]<<endl;pre[a[i]]=i;ans=max(ans,dp[i]+down[i+1]);}printf("%lld\n",ans);return 0;}