【CodeForces】CF10D LCIS

题目地址：

https://www.luogu.com.cn/problem/CF10D

题面翻译：
求两个串的最长公共上升子序列。

题目描述：
This problem differs from one which was on the online contest.

The sequence $a_1,a_2,...,a_n$ is called increasing, if $a_i<a_{i+1}$ for $i<n$ .

The sequence $s_1,s_2,...,s_k$ is called the subsequence of the sequence $a_1,a_2,...,a_n$ , if there exist such a set of indexes $1\le i_1<i_2<...<i_k\le n$ that $a_{i_j}=s_j$ . In other words, the sequence $s$ can be derived from the sequence $a$ by crossing out some elements.

You are given two sequences of integer numbers. You are to find their longest common increasing subsequence, i.e. an increasing sequence of maximum length that is the subsequence of both sequences.

输入格式：
The first line contains an integer $n$ ( $1\le n\le 500$ ) — the length of the first sequence. The second line contains $n$ space-separated integers from the range $[0,10^9]$ — elements of the first sequence. The third line contains an integer $m$ ( $1\le m\le 500$ ) — the length of the second sequence. The fourth line contains $m$ space-separated integers from the range $[0,10^9]$ — elements of the second sequence.

输出格式：
In the first line output $k$ — the length of the longest common increasing subsequence. In the second line output the subsequence itself. Separate the elements with a space. If there are several solutions, output any.

思路是动态规划。求最长公共子序列长度，可以参考https://blog.csdn.net/qq_46105170/article/details/114242851。设两个序列分别为$a$和$b$，设$f[i][j]$是$a[1:i]$和$b[1:j]$的最长公共上升子序列的长度，并且要求该子序列含$b[j]$。则： f [ i ] [ j ] = max ⁡ { f [ i − 1 ] [ j ] , 1 + max ⁡ k < j ∧ b [ k ] < a [ i ] f [ i − 1 ] [ k ] } f[i][j]=\max\{f[i-1][j],1+\max_{kf[i][j]=max{f[i−1][j],1+k<j∧b[k]<a[i]max​f[i−1][k]}当不含$a[i]$时，最长公共上升子序列长度即为$f[i-1][j]$；当含$a[i]$的时候，隐含$a[i]=b[j]$，可以以倒数第二个数是哪个来分类，如果不含倒数第二个数，则长度为$1$；如果倒数第二个数是$b[k],k<j$，隐含$b[k]<b[j]=a[i]$，则长度为$f[i-1][k]+1$。所以不含$a[i]$时，最长长度为 1 + max ⁡ k < j ∧ b [ k ] < a [ i ] { f [ i − 1 ] [ k ] } 1+\max_{k1+maxk<j∧b[k]<a[i]​{f[i−1][k]}。我们可以将$i$从$1\sim n$遍历，将$j$从$1\sim m$遍历，同时用一个变量$p$使得$p<j\wedge b[k]<a[i]$并且$f[i-1][p]$取到最大值。这样在内层循环里只需要常数的时间更新$f[i][j]$，同时只需要注意更新$p$即可。最后答案就是${\max }_{j}f[n][j]$。为了求具体序列，我们用一个二维数组$g[i][j]$表示使得$f[i][j]$取得最大值的时候，倒数第二个数在$b$中的下标（如果不存在倒数第二个数，则赋值为$0$）。那么要求具体序列，只需要找到使得$f[n][p]$最大的那个$p$，接着用$g[n][p]$替代$p$不停向前递推即可。代码如下：

#include 
using namespace std;

const int N = 510;
int n, m;
int a[N], b[N];
int f[N][N], pre[N][N];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) scanf("%d", &b[i]);

  for (int i = 1; i <= n; i++)
    for (int j = 1, p = 0; j <= m; j++) {
      f[i][j] = f[i - 1][j];
      pre[i][j] = pre[i - 1][j];
      if (a[i] == b[j] && f[i - 1][p] + 1 > f[i][j]) {
        f[i][j] = f[i - 1][p] + 1;
        pre[i][j] = p;
      }
      if (b[j] < a[i] && f[i - 1][j] > f[i - 1][p])
        p = j;
    }

  int res = 0, p;
  for (int i = 1; i <= m; i++)
    if (res < f[n][i]) {
      res = f[n][i];
      p = i;
    }

  printf("%d\n", res);

  m = res;
  while (p) {
    a[m--] = b[p];
    p = pre[n][p];
  }

  for (int i = 1; i <= res; i++) printf("%d ", a[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

时空复杂度$O(nm)$。