AcWing 272. 最长公共上升子序列

题目传送门

一、前导知识

二、本题思路

1、理解样例

2 2 1 3
2 1 2 3

两个序列，要求严格上升子序列，那么上面的那个序列中的严格上升子序列为

2 3
1 3

下面的序列中严格上升的子序列为

2 3
1 2
1 3

两个相同的，最长的为

1 3
2 3

长度是\(2\)，答案输出\(2\)。

2、解题关键

(1)状态表示

\(f(i,j)\)是以\(b[j]\)为结尾的\(LCIS\)（最长公共上升子序列）。

(2)状态计算

① \(f(i,j) = f(i-1,j)\) \((a[i] != b[j])\)

② \(f(i,j) = max(f(i-1,k)+1)\) \((1 <= k <= j-1 \&\& b[j] > b[k])\)

现在我们来说为什么会是这样的状态转移方程呢？

①:因为\(f(i,j)\)是以\(b[j]\)为结尾的\(LCIS\)，如果\(f(i,j)>0\),说明\(a[1]…a[i]\)中必然有一个\(a[k]\)等于\(b[j]\),如果\(a[k]!=a[i]\)，那么\(a[i]\)对\(f(i,j)\)没有贡献，不考虑它照样能得出\(f(i,j)\)的最优值。
所以在\(a[i]!=b[j]\)的情况下必然有\(f(i,j)=f(i-1)(j)\)。

②，前提是\(a[i] == b[j]\),我们需要去找一个最长的且能让\(b[j]\)接在其末尾的\(LCIS\)。之前最长的\(LCIS\)在哪呢？首先我们要去找的\(f\)数组的第一维必然是\(i-1\)。因为\(i\)已经拿去和\(b[j]\)配对去了，不能用了。并且也不能是\(i-2\)，因为\(i-1\)必然比\(i-2\)更优。第二维呢？那就需要枚举\(b[1]…b[j-1]\)了，因为你不知道这里面哪个最长且哪个小于\(b[j]\)。

三、实现代码O(N^3)

#include 

using namespace std;
const int N = 3010;

int n;      //此题目的数组长度，两个数组是一样的长度
int a[N];   //数组a
int b[N];   //数组b

/*二维DP数组，第一维表示数组a中第i个位置，第二维表示数组b中第j个位置，
并且以b[j]为结尾的上升子序列的集合，value=Max(集合内容)。
之所以这样定义数组的含义，可以参考LIS和LCS的思想，糅合到一起形成了这样一个二维状态表示。
*/
int f[N][N];

//朴素O(N^3)版本，N<=3000,所以3次方会超时，需要优化。
int main() {
    //读入数据
    cin >> n;
    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++)        //遍历a数组
        for (int j = 1; j <= n; j++) {  //遍历b数组
            //如果a[i]!=b[j]，那么a[i]无法为结果f[i][j]做出贡献 ，所以：f[i][j] = f[i - 1][j]
            if (a[i] != b[j]) f[i][j] = f[i - 1][j];
            else {
                //a[i]!=b[j]时很简单，麻烦的是相等
                //如果a[i]==b[j],那么f[i][j]的值就应该是前面a[1,i-1],b[1,j-1]中所有可能的最长上升公共子序列+1
                //如果没有其它的，那么还有a[i]==b[j]，最长的上升公共子序列值最小是1
                int Max = 1;
                /*具体是从哪个状态可以迁移到f[i][j]这个状态呢?不知道，需要逐个讨论一下。
                  (1)对于 1~j-1的每个b中元素，哪个可能是b[j]接上去形成最长上升子序列呢？都是有可能的，全部扫描一遍。
                  (2)对于k∈[1~j-1]，所有满足小于b[j]的f[i][k]都是有机会的，需要取它们的最大值。
                */
                for (int k = 1; k < j; k++)
                    if (b[k] < b[j])//只有可能接的上去的才有资格讨论
                        Max = max(Max, f[i - 1][k] + 1);//之所以+1,是因为a[i]=b[j]
                //更新f[i][j]的最大值
                f[i][j] = Max;
            }
        }
    //找出最大值
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, f[n][i]);
    printf("%d\n", res);
    return 0;
}

四、实现代码O(N^2)

#include 

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main() {
    //输入数据
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    //一般DP问题的优化，都是对朴素算法做等价变形。
    //本题的处理办法是将第三重循环优化掉,对代码做等价变形。

    //遍历a数组
    for (int i = 1; i <= n; i++) {
        //利用一个类似于前缀和的思路，减少一重循环，将O(N^3)变为O(N^2)
        int Max = 1;
        for (int j = 1; j <= n; j++) {//遍历b数组
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) f[i][j] = Max;
            //只有在a[i]>b[j]时，Max才会被更新
            if (a[i] > b[j]) Max = max(Max, f[i - 1][j] + 1);
        }
    }
    //输出结果
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
    printf("%d\n", res);
    return 0;
}

五、终极优化解法（一维+O(N^2)）

#include 

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N];
int res;

int main() {
    //输入数据
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    //一般DP问题的优化，都是对朴素算法做等价变形。
    //本题的处理办法是将第三重循环优化掉,对代码做等价变形。
    for (int i = 1; i <= n; i++) {
        int Max = 1;
        for (int j = 1; j <= n; j++) {
            if (b[j] < a[i]) Max = max(Max, f[j] + 1);
            if (b[j] == a[i]) f[j] = Max;
        }
    }
    //输出结果
    for (int i = 1; i <= n; i++) res = max(res, f[i]);
    printf("%d\n", res);
    return 0;
}