2013年8月15日

UVa 10635 - Prince and Princess

#include <cstdio>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;

int main() {
  int t, C = 1;
  scanf("%d", &t);
  while (t--) {
    int n, p, q;
    scanf("%d%d%d", &n, &p, &q);
    int pos[99999] = {};
    for (int i = 1, j; i <= p + 1; i++) {
      scanf("%d", &j);
      pos[j] = i;
    }
    vector<int> lcs;
    for (int i = 1, j; i <= q + 1; i++) {
      scanf("%d", &j);
      if (!pos[j]) {
        continue;
      }
      int p = pos[j];
      if (!lcs.size() || p > lcs.back()) {
        lcs.PB(p);
      } else {
        *lower_bound(lcs.begin(), lcs.end(), p) = p;
      }
    }
    printf("Case %d: %d\n", C++, lcs.size());
  }
  return 0;
}

沒有留言:

張貼留言