CF10D LCIS

题意

求两个串的最长公共上升子序列。

n,m<=500

分析

表示 A 与 B 构成的以 为结尾的 LCIS 的长度:

时间复杂度 .

#include<iostream>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;

int n,m,mx,mxn;
int a[600],b[600],f[600][600],pre_b[600];

void print_pre(int nk){
    if(!nk)return;
    print_pre(pre_b[nk]);
    cout<<b[nk]<<' ';
}
int main(){
    cin>>n;
    FOR(i,1,n)cin>>a[i];
    cin>>m;
    FOR(i,1,m)cin>>b[i];
    FOR(i,1,n)FOR(j,1,m)f[i][j]=1;
    FOR(i,1,n)FOR(j,1,m){
        if(a[i]!=b[j])f[i][j]=f[i-1][j];
        else {
            for(int k=j-1;k>=0;k--)if(b[k]<b[j]&&f[i][j]<f[i-1][k]+1)
                f[i][j]=f[i-1][k]+1,pre_b[j]=k;
        }
    }
    FOR(i,1,m)if(f[n][i]>mx)mx=f[n][i],mxn=i;
    cout<<mx<<endl;
    print_pre(mxn);
    return 0;
}

  转载请注明: Sshwy's Blog CF10D LCIS

 上一篇
毒瘤 % 你赛 毒瘤 % 你赛
毒瘤 % 你赛 题面A.pdfB.pdfC.pdfD.pdf A.Prefix Sum 写一个表就发现是杨辉三角 于是裸的组合数 模数是质数,用费马小定理算逆元即可。```cppincludeusing namespace std;type
2018.10.01
下一篇 
IOI1999 花店橱窗布置 IOI1999 花店橱窗布置
分析动态规划法,用 表示用了 朵花,摆了 个花瓶的最大美学值 (不一定要摆第 个花瓶), 表示第 i 朵花摆第 个花瓶中最大的一个花瓶的美学值 f[i,j]=\ma
2018.10.01
  目录