1082E. Increasing Frequency
程序员文章站
2024-03-19 09:24:58
...
记录左边更优方案的方法很有趣
一开始没想出来
//cyc
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mst(a) memset(a,0,sizeof a)
using namespace std;
typedef pair<int,int> pii;
/*
もう一回、もう一回!
*/
const int maxn=5e5+5;
const int maxp=1e6+5;
int a[maxn];
int vis[maxn];
int suf[maxn];
int pref[maxn];
int lans[maxn];
int lst[maxn];
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,c;
cin>>n>>c;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
pref[i]=pref[i-1];
if(a[i]==c){
pref[i]++;
}
}
for(int i=n;i>=1;i--){
suf[i]=suf[i+1];
if(a[i]==c){
suf[i]++;
}
}
for(int i=1;i<=n;i++){
int p=lst[a[i]];
lans[i]=pref[i-1]+1;
lans[i]=max(lans[i],lans[p]+1);
lst[a[i]]=i;
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,lans[i]+suf[i+1]);
}
cout<<ans<<endl;
}
推荐阅读
-
1082E. Increasing Frequency
-
CF1082E Increasing Frequency (multiset+乱搞+贪心)
-
Codeforces.1082E.Increasing Frequency(思路)
-
[CF1082E] Increasing Frequency
-
codeforces 1082E Increasing Frequency
-
CodeForces -1168A Increasing by Modulo(二分答案)
-
实现一个输出字符串中各个字符出现的频率frequency函数
-
【洛谷_CF261D】Maxim and Increasing Subsequence
-
mysql Sort aborted: Out of sort memory, consider increasing server sort buffer s
-
LeetCode-3.14-300-M- 最长上升子序列(Longest Increasing Subsequence)