E2. Three Blocks Palindrome (hard version)

我们考虑一种最优构造
对于一个数x 我们肯定要的是他的前几个 再最后几个 中间选最多的一个数
这样显然是最优的
我们枚举x 再枚举前面要的长度
中间选的最多的一个数可以通过logn求解
总的时间复杂度是O（nvlogn）

int n,a[N];
vector<int>st[201];
int find(int i,int x){return lower_bound(all(st[i]),x)-st[i].begin();}
int find1(int i,int x) {return upper_bound(all(st[i]), x) - st[i].begin();}
int query(int l,int r){
    int res=0;
    for(int i=1;i<=201;i++)
        res=max(res,find1(i,r)-find(i,l));
    return res;
}
void solve(){
    cin>>n;
    for(int i=1;i<=200;i++)st[i].clear();
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st[a[i]].push_back(i);
    }
    int ans=1;
    for(int x=1;x<=200;x++){
        for(int len=1;len<=st[x].size();len++){
            int l=st[x][len-1],r=st[x][st[x].size()-len];
            if(l>=r)break;
            ans=max(ans,len*2+query(l+1,r-1));
        }
    }
    cout<<ans<<endl;
}

原文地址：http://www.cnblogs.com/ycllz/p/16852850.html