mzoj114【SR的复活赛 T3】最长回文子序列

Algorithm：树状数组优化DP

性质：相同数对少，实际状态少

朴素dp：dp[i][j]=max(dp[k][l]+2)——如果a[i]==a[j]

由于每个数字最多只出现4次，所以数对数量不超过C(4,2)/4*1e5

f[k]表示dp[a[k].first][a[k].second]，用一个包含于[a[k].first，a[k].second]的区间更新f[k]，需要满足左端点大于a[k].first，右端点小于a[k].second，则问题转化为一个二维偏序问题，先排序，再用树状数组维护最大值即可

代码：

/*
Algorithm：树状数组优化DP
性质：相同数对少，实际状态少
author：white-star
*/
#include<bits/stdc++.h>
using namespace std;

#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define fo(i,a) for(int i=0;i<a;++i)
#define mem(a,b) memset(a,b,sizeof(a))
#define il inline
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define lowbit(x) (x&-x)

const int inf=0x3f3f3f3f,N=1e5+10;
typedef pair<int,int> pai;

int n,m,f[N],c[N];
vector<int>v[N];
pai a[N];

il void read(int &x){
    x=0;char c=getchar(),f=1;
    while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
    while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
    x*=f;
}
il void add(int x,int y){
    for(;x<=m;x+=lowbit(x)) c[x]=max(c[x],y);
}
il int ask(int x){
    int ans=0;
    for(;x;x-=lowbit(x)) ans=max(ans,c[x]);
    return ans;
}

void work(){
    mem(c,0);
    int x;
    read(m),read(x);
    go(i,1,100000) v[i].clear();
    go(i,1,m){
        read(x);
        v[x].pb(i);
    }
    n=0;
    go(cur,1,100000)
        fo(i,v[cur].size())
            for(int j=i+1;j<v[cur].size();++j)
                a[++n]=mp(v[cur][i],v[cur][j]);
    sort(a+1,a+n+1,greater<pai>());
    for(int i=1,j=1;i<=n;i=j+1,j=i){
        while(j<n&&a[j].fi==a[j+1].fi) ++j;
        go(k,i,j) f[k]=max(ask(a[k].se-1),int(a[k].fi+1!=a[k].se))+2;
        go(k,i,j) add(a[k].se,f[k]);
    }
    cout<<max(ask(m),1)<<endl;
}

int main(){
    //freopen("input.txt","r",stdin);
    int T;read(T);
    while(T--) work();
    return 0;
}