UVA 10635: Prince and Princess —— LCS 转 LIS

题目链接

题目大意:

给定一个 $n \times n$ 的棋盘和两个数组。第一个数组 $a[]$ 有 $p + 1$ 个元素,第二个数组 $b[]$ 有 $q + 1$ 个元素,每个数组里的数各不相同,且两个数组都以 $n \times n$ 结尾。求: 这两个数组的最长公共子序列。

输入格式:

第一行一个数 $T$ , 代表测试数据数量。

对于每组测试数据,第一行三个整数 $n, p, q$ ( $n \leq 250,\ p,q \leq n \times n$ ),第二行 $p + 1$ 个数,代表数组 $a$ ,第三行 $q + 1$ 个数,代表数组 $b$ 。

输出格式:

对于每组测试数据,输出其最长公共子序列的长度。格式与样例一致。

测试样例:

Input
1
3 6 7
1 7 5 4 8 3 9
1 4 3 5 6 2 8 9
Output
Case 1: 4

分析:

之所以把这道题放上来,不是因为这道题难,而是因为这道题涉及到了一个以前从未接触过的东西,叫做最长公共子序列 ( LCS ) 转最长上升子序列 ( LIS )。

首先我们都知道,求 LCS 有一个经典的动态规划的 $O(n ^ 2)$ 的方法。这个方法在这里显然是不能用的,因为 $O((n \times n) ^ 2)$ 在这里显然是不能接受的。所以我们需要把 LCS 问题转化为 LIS 问题,用 LIS 的 $O(nlogn)$ 的方法解决。

如何操作呢?

假设 $a[]$ = {$1, 2, 3, 4 ,5$}, $b[]$ = {$2, 5, 4, 2, 4$} 。

我们要找出 $a[]$ 中的元素在 $b$ 中的位置 (如果没有就跳过) 。在这个例子中 $2$: {$1, 4$},$4$: {$3, 5$}, $5$: {$2$} 。接下来把每个元素对应位置数组中的元素降序排列,变成 $2$: {$4, 1$}, $4$: {$5, 3$}, $5$: {$2$} 。将这些元素对应的数组按元素在 $a[]$ 中的顺序构造成一个新数组 $t[]$ = {$4, 1, 5, 3, 2$} ,对这个新的 $t[]$ 数组求 LIS ,就得到了答案。

对于这道题,因为数组不重复,所以不存在降序排列的问题,直接映射就好。

代码

  • 根据 imbiansl 的反馈,修改了代码中的一处错误。之前的代码之所以可以 AC 是因为该错误不影响答案,只是有失严谨。 —— 2017. 10. 20
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

template<typename _T> inline void read(_T &_x) {
  int _t, _flag = 0;
  while ((_t = getchar()) != '-' && ( _t < '0' || _t > '9'));
  if (_t == '-')  _t = getchar(), _flag = 1;
  _x = _t - '0';
  while ((_t = getchar()) >= '0' && _t <= '9')
    _x = _x * 10 + _t - '0';
  if (_flag)  _x = -_x;
}

typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 250 * 250 + 100, INF = 0x3f3f3f3f;
int n, p, q;
int a[MAX_N], b[MAX_N], t[MAX_N], pos[MAX_N], dp[MAX_N], c[MAX_N];
int ina[MAX_N], cnt;

void init() {
  memset(a, 0, sizeof(a));
  memset(b, 0, sizeof(b));
  memset(t, 0, sizeof(t));
  memset(pos, -1, sizeof(pos));
  memset(dp, 0, sizeof(dp));
  memset(ina, 0, sizeof(ina));
}

void get_t() {
  cnt = 0;
  for (int i = 1; i <= p + 1; ++i)
    if (pos[a[i]] != -1)  t[++cnt] = pos[a[i]];
}

int LIS(int *tp) {
  memset(c, INF, sizeof(c));
  int ans = 0;
  for (int i = 1; i <= cnt; ++i) {
    dp[i] = lower_bound(c + 1, c + cnt + 1, tp[i]) - c;
    c[dp[i]] = tp[i];
    ans = max(ans, dp[i]);
  }
  return ans;
}

int main() {
  int T;
  read(T);
  int kase = 0;
  while (T--) {
    init();
    read(n), read(p), read(q);
    for (int i = 1; i <= p + 1; ++i) {
      read(a[i]);
      ina[a[i]] = 1;
    }
    for (int i = 1; i <= q + 1; ++i) {
      read(b[i]);
      if (ina[b[i]])  pos[b[i]] = i;
    }
    get_t();
    int ans = LIS(t);
    printf("Case %d: %d\n", ++kase, ans);
  }
}