【专题】Subsequence

回文子序列

----------------------------

最长回文子序列

题目略

----------------------------

这是回文子序列的基础，直接DP即可。

f[ L ][ R ] 表示区间[ L , R ] 的最长回文子序列长度。

f[ L ][ R ] = 0 ( L > R )

f[ L ][ R ] = 1 ( L = R )

f[ L ][ R ] = f[ L+1 ][ R-1 ] + 2 ( S[ L ]==S[ R ] )

f[ L ][ R ] = max( f[ L+1 ][ R ] , f[ L ][ R-1 ] )

----------------------------

代码略

----------------------------

环形回文子序列

HDU 4745 Two Rabbits

----------------------------

重点是用next() prev() 代替l+1,r-1

在普通的回文子序列dp中若x>y 则 f[ x ][ y ]没有值

这为环形dp提供了储存空间。

----------------------------

const int maxn=1111;
int a[maxn];
int f[maxn][maxn];
int n;
int prev(int x){
    return (x-1+n)%n;
}
int next(int x){
    return (x+1)%n;
}

int dp(int l,int r){
    if (l==r) return 1;
    if (next(l)==r) return 1+(a[l]==a[r]);
    if (f[l][r]!=-1) return f[l][r];
    if (a[l]==a[r]) return f[l][r]=dp(next(l),prev(r))+2;
    return f[l][r]=max(dp(next(l),r),dp(l,prev(r)));
}

int main()
{
    int ans;
    while (~scanf("%d",&n)){
        if (n==0) break;
        ans=0;
        memset(f,-1,sizeof(f));
        for (int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        if (n==1) ans=1;
        else if (n==2) ans=2;
        else{
            for (int i=0;i<n;i++){
                ans=max(ans,dp(next(i),prev(i))+1);
                //ans=max(ans,dp(i,prev(i)));
                ans=max(ans,dp(next(i),i));
            }
        }
        printf("%d
",ans);
    }
    return 0;
}

----------------------------

超长回文子序列

Codeforces 335 B-Palindrome

----------------------------

题目给出的n范围较大(5*10^5)，要求输出长度为100的回文子序列，若不存在则输出最长的。

注意到隐含条件，序列由小写字母构成，当n>=2600时，必然有某个字母的数量超过100（鸽笼原理），输出100个该字母即可。

注意输出dp方案的思路。

此题也可以用纯dp优化解决。

见题解： http://codeforces.com/blog/entry/8538

代码： http://codeforces.com/contest/335/submission/4221965

----------------------------

const int maxs=55555;
const int maxn=3333;
char s[maxs];
int n;
int cnt[27];
char mc;
char ans[maxs];
int t;
int f[maxn][maxn];
int dp(int l,int r){
    if (l>r) return 0;
    if (l==r) return 1;
    //if (l+1==r) return 1+(s[l]==s[r]);
    if (f[l][r]!=-1) return f[l][r];
    if (s[l]==s[r]) return f[l][r]=dp(l+1,r-1)+2;
    return f[l][r]=max(dp(l,r-1),dp(l+1,r));
}
void trace(int l,int r){
    if (l>r) return;
    if (l==r) ans[t++]=s[l];
	else if (s[l]==s[r]){
		ans[t++]=s[l];
		trace(l+1,r-1);
		ans[t++]=s[r];
	}
	else{
		if (f[l+1][r]<f[l][r-1]) trace(l,r-1);
		else trace(l+1,r);
	}
}

int main()
{
    cin>>(s+1);
    n=strlen(s+1);
    memset(cnt,0,sizeof(cnt));
    if (n>=2600){
        for (int i=1;i<=n;i++){
            cnt[s[i]-'a']++;
        }
        for (int i=0;i<26;i++){
            if (cnt[i]>=100){
                mc=i+'a';
                break;
            }
        }
        for (int i=0;i<100;i++){
            ans[i]=mc;
        }
        ans[100]=0;
        cout<<ans<<endl;
    }
    else{
        memset(f,-1,sizeof(f));
        dp(1,n);
        t=0;
        trace(1,n);
        ans[t]=0;
        //cerr<<"nice"<<endl;
        if (t<=100) cout<<ans<<endl;
        else{
            //cout<<"boy next door"<<endl;
            for (int i=0;i<50;i++) cout<<ans[i];
            for (int i=t-50;i<t;i++) cout<<ans[i];
            cout<<endl;
        }
    }
    return 0;
}

----------------------------