【动态规划】线性dp——LIS和LCS-EW帮帮网

子序列

一个序列 $A＝a_1,a_2,…,a_n$ 中任意删除若干项，剩余的序列叫做 A 的一个子序列。也可以认为是从序列 A 按原顺序保留任意若干项得到的序列。（例如：对序列｛1,3,5,4,2,6,8,7｝来说，序列｛3,4,8,7｝是它的一个子序列。）

LIS 最长上升子序列

代码

转移方程： $d p [i] = ma x (d p [i], d p [j] + 1)$

O(n2)

const int N=5010;
int n;
int a[N],dp[N],ans;
signed main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        dp[i]=1;//自己是一个数列
        for(int j=0;j<i;j++){
            if(a[i]>a[j]){//上升
                dp[i]=max(dp[i],dp[j]+1);//找之前的数列
                ans=max(dp[i],ans);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

O(nlogn)

//O(nlogn)做法 
//下降序列
int ans=1,dp[N]={0};
dp[1]=a[1];
for(int k=2;k<=i;k++){
    if(a[k]<=dp[ans]){
        //更小的向后取组成序列
        ans++;
        dp[ans]=a[k];//下降的序列
    }else{//跟最后的比不下降 就放前面相当于重开一个序列
        //dp下降 用greater<>
        int j=upper_bound(dp+1,dp+1+ans,a[k],greater<int>())-dp;
        //二分 找第一个小于a[k]的数
        dp[j]=a[k];//开下降序列
    }
}
//上升序列
int ans=1,dp[N]={0};
dp[1]=a[1];
for(int k=2;k<=i;k++){
    if(a[k]>dp[ans]){
        ans++;
        dp[ans]=a[k];
    }else{
        //dp上升
        int j=upper_bound(dp+1,dp+1+ans,a[k])-dp;
        //二分 找第一个大于a[k]的数
        dp[j]=a[k];
    }
}

例题

P1020 导弹拦截

构造下降序列找导弹数目，上升序列找系统数目。
二分查找 O(nlogn)做法
细节见代码。

signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int i=1;
    while(cin>>a[i])i++;
    i--;
    //能拦截多少导弹
    int ans=1;
    dp[1]=a[1];
    for(int k=2;k<=i;k++){
        if(a[k]<=dp[ans]){//每一发炮弹都不能高于前一发的高度
            //比前一发低，记录数目
            ans++;
            dp[ans]=a[k];//构造一个下降的序列
        }else{
            //dp下降
            int j=upper_bound(dp+1,dp+1+ans,a[k],greater<int>())-dp;
            //二分 找第一个小于a[k]的数 相当于新开一个系统 新开一个下降序列
            dp[j]=a[k];//开下降序列
        }
    }
    cout<<ans<<endl;
    
    //用多少系统
    int cnt=1;
    x[1]=a[1];
    for(int k=2;k<=i;k++){
        if(x[cnt]<a[k]){//新开一个系统
            cnt++;
            x[cnt]=a[k];//x是上升序列
        }
        else{
            int j=lower_bound(x+1,x+cnt+1,a[k])-x;//找第一个大于等于a[k]的系统 能拦截这个炮弹
            x[j]=a[k];
        }
        // for(int m=1;m<=cnt;m++)cout<<x[m]<<' ';
        // cout<<endl;
    }
    cout<<cnt;
    return 0;
}

P2782 排序+LIS

const int N=2e5+10;
struct fr{
    int a,b;
}c[N];
int dp[N];
void solve(){
    int n;cin>>n;
    forr(i,1,n){
        cin>>c[i].a>>c[i].b;
    }
    sort(c+1,c+1+n,[](fr x,fr y){
        return x.a<y.a;
    });

    //找LIS
    int ans=1;
    /*
    //超时
    forr(i,1,n){
        dp[i]=1;
        forr(j,1,i-1){
            if(c[i].b>c[j].b){
                dp[i]=max(dp[i],dp[j]+1);
                ans=max(dp[i],ans);
            }
        }
    }
    */
   dp[1]=c[1].b;
   forr(i,2,n){
        if(c[i].b>dp[ans]){
            ans++;
            dp[ans]=c[i].b;
        }else{
            int j=upper_bound(dp+1,dp+ans+1,c[i].b)-dp;//替换第一个大于c[i].b的
            dp[j]=c[i].b;
        }
   }
    cout<<ans<<endl;
}

P1091 两次LIS

const int N=2e5+10;
int dp[N],dpr[N];
void solve(){
    int n;cin>>n;
    vector<int>t(n+1);
    forr(i,1,n){
        cin>>t[i];
    }
    int maxn=0;
    forr(i,1,n){
        // dp[i]=1;
        forr(j,1,i-1){
            if(t[i]>t[j])dp[i]=max(dp[j]+1,dp[i]);
        }
    }
    reforr(i,1,n){
        // dpr[i]=1;
        reforr(j,i+1,n){
            if(t[i]>t[j])dpr[i]=max(dpr[j]+1,dpr[i]);
        }
    }
    forr(i,1,n){
        // cout<<dp[i]<<' '<<dpr[i]<<' '<<dp[i]+dpr[i]<<endl;
        maxn=max(dp[i]+dpr[i]+1,maxn);
    }
    cout<<n-maxn<<endl;
}

LCS 最长公共子序列

代码

在这里插入图片描述
状态转移方程 $d p [i] [j] = ma x (d p [i - 1] [j], d p [i] [j - 1], d p [i - 1] [j - 1] + 1)$ ，dp是LCS的长度。

forr(i,1,len){
    forr(j,1,len){
        if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+1;
        else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    }
}

例题

P1435

回文从前面看后面看都是一样的，所以思路就是将原字符串和逆转后的字符串找LCS，就是已经回文的。总长减去回文的就是不回文的。

const int N=1e3+10;
int dp[N][N];
void solve(){
    string s;cin>>s;
    string rs=string(s.rbegin(),s.rend());
    int len=s.size();
    forr(i,1,len){
        forr(j,1,len){
            if(s[i-1]==rs[j-1])dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    cout<<len-dp[len][len];
}

LCIS 最长公共上升子序列

模板题

状态转移方程：

在这里插入图片描述
两重循环i、j分别遍历a、b数组，另有一个k，O(n3)。

$a[i]\neq b[j]$ ：确定 $i$ 后，每次遍历 $j$ ，从上一个确定的 $d p [i - 1] [j]$ 转移过来
$a [i] = b [j]$ ：如果相等，从 $b [j] > b [k]$ 的 $k$ 位置+1，找最大值

优化

k遍历的是 $1\leq k \leq j-1$ ，可以在遍历j的同时更新 $ma x (d p [i - 1] [j])$ 用到j+1的更新中
参考文章

//优化前
 for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            f[i][j] = f[i - 1][j];      // 枚举所有不包含a[i]的上升公共子序列
            if (a[i] == b[j]) {
                f[i][j] = max(f[i][j], 1);      // 更新空集
                for (int k = 1; k < j; ++k) 
                    if (b[k] < b[j])            
                        f[i][j] = max(f[i][j], f[i][k] + 1);
            }
        }
//原文链接：https://blog.csdn.net/yl_puyu/article/details/109781829

//优化后
forr(i,1,n){//对a数组每一个数
    int val=0;
    forr(j,1,m){//跟b数组中匹配 以b[j]为结尾
        dp[i][j]=dp[i-1][j];//从上一个a中的数转移过来
        //是公共序列
        if(a[i]==b[j])dp[i][j]=max(val+1,dp[i][j]);
        //优化  b[j]<a[i]相当于b[1...j-1]<b[j]
        if(b[j]<a[i])val=max(dp[i-1][j],val);//更新最大值
    }
}
int ans=0,ansj;
forr(j,1,m){
    if(ans<dp[n][j])ans=dp[n][j],ansj=j;
}
cout<<ans;

再加记录序列：
但是提交之后一直RE 卡了一小时不知道哪里出问题了

const int N=510;
int dp[N];
int a[N],b[N];
vector<int>sq[N];
void solve(){
    int n,m;
    cin>>n;
    forr(i,1,n)cin>>a[i];
    cin>>m;
    forr(i,1,m){
        cin>>b[i];
        // sq[i]=vector<int>();
    }
    forr(i,1,n){//对a数组每一个数
        // int val=0;
        int mj=0;
        forr(j,1,m){//跟b数组中匹配
            //优化  b[j]<a[i]相当于b[1...j-1]<b[j]
            //dp保持j-1状态
            if(b[j]<a[i]&&dp[j]>dp[mj]){
                // val=max(dp[i-1][j],val);//更新最大值
                // val=dp[j];
                mj=j;
            }
            // dp[i][j]=dp[i-1][j];//从上一个a中的数转移过来
            //以b[j]为结尾 是公共序列
            if(a[i]==b[j]){
                dp[j]=max(dp[mj]+1,dp[j]);
                sq[j]=sq[mj];
                sq[j].push_back(b[j]);
            }
        }
    }
    int ans=0,ansj=1;
    forr(j,1,m){
        if(dp[ansj]<dp[j])ans=dp[j],ansj=j;
    }

    cout<<dp[ansj]<<endl;
    forr(i,0,sq[ansj].size()-1){
        cout<<sq[ansj][i]<<' ';
    }
}

让豆包改了之后这样：

void solve() {
    int n, m;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> m;
    vector<int> b(m + 1);
    vector<int> dp(m + 1, 0);
    vector<vector<int>> sq(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    for (int i = 1; i <= n; i++) {
        int mj = 0;
        for (int j = 1; j <= m; j++) {
            if (b[j] < a[i] && dp[j] > dp[mj]) {
                mj = j;
            }
            if (a[i] == b[j]) {
                if (dp[mj] + 1 > dp[j]) {
                    dp[j] = dp[mj] + 1;
                    sq[j] = sq[mj];
                    sq[j].push_back(b[j]);
                }
            }
        }
    }

    int ans = 0, ansj = 1;
    for (int j = 1; j <= m; j++) {
        if (dp[ansj] < dp[j]) {
            ans = dp[j];
            ansj = j;
        }
    }

    cout << dp[ansj] << endl;
    for (int i = 0; i < sq[ansj].size(); i++) {
        cout << sq[ansj][i] << ' ';
    }
    cout << endl;
}

【动态规划】线性dp——LIS和LCS

子序列