时间戳

首页 > 技术文章 > 【线性dp】B001_AW_最长公共上升子序列 & 密码脱落（暴力dp / 代码等价变换优化）

【线性dp】B001_AW_最长公共上升子序列 & 密码脱落（暴力dp / 代码等价变换优化）

wdt1 2020-09-07 20:43 原文

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。
小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。
小沐沐说，对于两个数列A和B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。
奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。
不过，只要告诉奶牛它的长度就可以了。
数列A和B的长度均不超过3000。

输入格式
第一行包含一个整数N，表示数列A，B的长度。
第二行包含N个整数，表示数列A。
第三行包含N个整数，表示数列B。
输出格式
输出一个整数，表示最长公共上升子序列的长度。
数据范围
1≤N≤3000,序列中的数字均不超过\(2^{31}−1\)

输入样例：
4
2 2 1 3
2 1 2 3
输出样例：
2

方法一：暴力dp

  • 定义状态：
    • f[i][j] 表示包含所有A[0..i]和B[0...j]且以B[j]结尾的最长LMIS的长度
  • 思考初始化：
    • f[i] =
  • 思考状态转移方程：有两种情况，
    • f[i][j]=f[i-1][j]，表示不包含A[i]的LMIS
    • if(A[i]==B[j])，f[i][j]=max(f[i-1][k])，if(B[k]<A[i])，k∈[1,j])，如果包含A[i]，则前提是 A[i]=B[j]，且 B[k] 都小于 A[i]；而又因为以B中的什么元素结尾不知道所以，需要枚举所有已有情况
  • 思考输出：f[n][n]

mle，tle...

#include<bits/stdc++.h>
using namespace std;
typedef int ll;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n; cin>>n;
    ll A[n+1], B[n+1], f[n+1][n+1]; memset(f,0,sizeof f);
    for (int i=1; i<=n; i++) cin>>A[i];
    for (int i=1; i<=n; i++) cin>>B[i];
    
    for (int i=1; i<=n; i++)
    for (int j=1; j<=n; j++) {
        f[i][j]=f[i-1][j];
        if (A[i]==B[j]) {
            ll mx=1;
            for (int k=1; k<j; k++) if (B[k]<B[j]) {
                mx=max(mx, f[i-1][k]+1);
            }
            f[i][j]=max(f[i][j], mx);
        }
    }
    int ans=1;
    for (int i=1; i<=n; i++) if (f[n][i]>ans)
        ans=f[n][i];
    cout << ans;
    return 0;
}

复杂度分析

  • Time：\(O(n^3)\)，
  • Space：\(O(n^2)\)，

方法二：优化

可以一边枚举 j 的时候顺便枚举 mx，即f[i-1][j]的值，

#include<bits/stdc++.h>
using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n; cin>>n;
    int A[n+1], B[n+1], f[n+1][n+1]; memset(f,0,sizeof f);
    for (int i=1; i<=n; i++) cin>>A[i];
    for (int i=1; i<=n; i++) cin>>B[i];
    
    for (int i=1; i<=n; i++) {
        int mx=1;
        for (int j=1; j<=n; j++) {
            f[i][j]=f[i-1][j];
            if (B[j]<A[i])  mx=max(mx, f[i-1][j]+1);
            if (A[i]==B[j]) f[i][j]=max(f[i][j], mx);
        }
    }
    int ans=*max_element(f[n]+1, f[n]+n+1);
    cout << ans;
    return 0;
}

复杂度分析

  • Time：\(O(n^2)\)，
  • Space：\(O(n^2)\)，

二、密码脱落

密码串当初应该是前后对称的；给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

输入格式
共一行，包含一个由大写字母ABCD构成的字符串，表示现在看到的密码串。
输出格式
输出一个整数，表示至少脱落了多少个种子。
数据范围
输入字符串长度不超过1000

输入样例1：
ABCBA
输出样例1：
0
输入样例2：
ABDCDCBABC
输出样例2：
3

方法一：线性dp

要改变多少个字符才能使 s[l:r] 变为镜像，s.size() - (reverse_s 和 s 的最长公共子序列的长度) 就是答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string A; cin>>A;
    string B=A;
    reverse(B.begin(), B.end());

    if (B==A) {
        cout << 0;
    } else {
        int n=A.size(), f[n+1][n+1]; memset(f, 0, sizeof f);
        for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++) {
            if (A[i-1]==B[j-1]) f[i][j]=f[i-1][j-1]+1;
            else                f[i][j]=max(f[i-1][j], f[i][j-1]);
        }
        cout << n-f[n][n];
    }
    return 0;
}

推荐阅读