做网站合同/app软件开发

https://vjudge.net/problem/CodeForces-1335E2

题目大意：给一个数组，要你找到一个最长的子序列，使得它满足以下形式，其中$a$和$b$可以相等。$x、y>=0$。

思路：我们把这三段命名为左中右，通过枚举左边这一段的结束位置就可以计算出正确答案。假设当前枚举的位置是$i$，那么$[1\dots i]$这段子序列应该取什么颜色呢？其实取$a[i]$就可以了，因为其它的颜色要么在$[1\dots i-1]$枚举过了，要么还没出现。那么知道了左边这一段的颜色，而右边这一段的颜色和左边是相等的且出现的次数要一致，假设在区间$[y+1\dots n]$内颜色$a[i]$也出现了相同的次数，不妨设为$ct$，此时留给中间段的区间只剩下$[i+1,y]$了，那么我们可以枚举所有的颜色，取在这段区间中出现次数最多的那种，不妨设为$MAX$，那么这种情况下的最佳结果就是$2\ast ct+MAX$。现在问题就是如何在已知$a[i]、ct$的情况下，求出这个$y$。我们可以搞一个$colr[color\_num][n]$，用$colr[i][j]$表示颜色$i$倒数第$j$次出现的位置，显然这个数组可以$O(n)$预处理出来，而且可以在$O(1)$内得到$y$。那么问题就解决了，总复杂度$O(n\ast color\_num)$。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pr pair<int,int>
using namespace std;
typedef long long ll;const int maxn=2e5+5;
const int num=200;int t,n;
int a[maxn],cnt[maxn][205];
vector<int> colr[205];int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);for(int j=1;j<=num;j++)cnt[i][j]=cnt[i-1][j];++cnt[i][a[i]];}for(int i=n;i>=1;i--)colr[a[i]].push_back(i);int ans=0,MAX,y,color,ct;for(int i=1;i<=n;i++){ct=cnt[i][a[i]];ans=max(ans,ct);color=a[i];if(colr[color].size()<ct)continue;y=colr[color][ct-1]-1;if(y<i+1)continue;MAX=0;for(int k=1;k<=num;k++) //中间部分的区间为 [i+1,y]MAX=max(MAX,cnt[y][k]-cnt[i][k]);ans=max(ans,ct*2+MAX);}printf("%d\n",ans);for(int i=1;i<=num;i++)colr[i].clear();}return 0;
}