CDOJ1300 LCIS

这道题当初想当然的认为 LCIS 只要求出 LCS 记录路径然后求 LCS 的 LIS 就可以，发现根本不是这回事儿。。

这题很明显的 dp，但是转移方程写的各种戳。。。。- -

最裸的 dp 方程：

$$dp[i][j]=\max\{dp[k_i][k_j]\}+1$$

其中：

$$\begin{cases} k_i<i \\ k_j<j \\ a_i = a_{k_i} \\ b_j = b_{k_j} \end{cases}$$

$dp[i][j]$ 表示以 $a_i$ 和 $b_j$ 结尾的 LCIS。

这样转移正确性就不做证明了，很明显，但是转移费用太高了，是 $O(n^2)$ 的转移，这样总的时间复杂度就变成了 $O(n^4)$。对于$1000$ 的数据不可接受。

改进版本：

$$dp[i][j] = \max\{dp[k_i][j-1]\}+1$$

其中：

$$\begin{cases} ki<i \\ a_i = b_j \end{cases}$$

这时候 $dp[i][j]$ 表示以 $a_i$ 结尾，$b_j$ 或其之前元素结尾的 LCIS。

这样转移就可以写成 $O(n)$ 的转移，加上 $O(n^2)$ 的状态，算法复杂度是 $O(n^3)$。

注意，这时候还有一个很显著的优化，记录一个下标 $p$ 使得 $a_p \leq b_j$ 并且 $dp[p][j-1]$ 是 $dp[0][j-1]$ 到 $dp[i-1][j]$ 中最大的，这样转移就是 $O(1)$ 的

$$dp[i][j]=dp[p][j-1]+1$$

至此，我们的 $O(n^2)$ 的 dp 方程就已经完成，总的复杂度就是 $O(n^2)$，对于 $1000$ 的数据量正好适合

我的代码：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAX = 1100;
int dp[MAX][MAX], a[MAX], b[MAX];

int get() {
  char ch;
  int flag = 0, tmp = 0;
  for (ch = getchar(); ch < 48 || ch > 57; ch = getchar())
    if (ch == int('-')) break;
  if (ch == int('-'))
    flag = 1;
  else
    tmp = int(ch) - 48;
  for (ch = getchar(); 48 <= ch && ch <= 57; ch = getchar())
    tmp = tmp * 10 + int(ch) - 48;
  return (flag) ? -tmp : tmp;
}

int main() {
  int t;
  int lena, lenb;
  t = get();
  while (t--) {
    lena = get();
    lenb = get();
    for (int i = 1; i <= lena; i++) a[i] = get();
    for (int i = 1; i <= lenb; i++) b[i] = get();
    for (int i = 0; i <= lena; i++) dp[i][0] = 0;
    for (int j = 1; j <= lenb; j++) {
      dp[0][j] = 0;
      int p = 0;
      for (int i = 1; i <= lena; i++) {
        dp[i][j] = dp[i][j - 1];
        if (a[i] == b[j] && dp[i][j] < dp[p][j - 1] + 1) {
          dp[i][j] = dp[p][j - 1] + 1;
        } else if (a[i] < b[j] && dp[i][j] > dp[p][j - 1]) {
          p = i;
        }
      }
    }
    int ret = 0;
    for (int i = 0; i <= lena; i++) {
      ret = max(ret, dp[i][lenb]);
    }
    printf("%d\n", ret);
  }
  return 0;
}