a664. CPE：Prince and Princess (UVa 10635)

題目描述

在 n × n 的棋盤上，每格依序編號 1 到 n^2。王子與公主各從 1 出發，分別跳 p 次與 q 次，最後抵達 n^2；各自的路徑不會重複拜訪同一格。

國王希望兩人略過部分跳躍，形成完全相同的共同路徑，而且保留的格子順序不得改變。請找出最長共同路徑的格子數，也就是兩條路徑的最長共同子序列長度，包含起點與終點。

輸入格式

第一行是測試資料筆數 t，1 ≤ t ≤ 10。每筆第一行有 n、p、q，2 ≤ n ≤ 250，1 ≤ p,q < n^2。

第二行是王子的 p + 1 個不同格子編號；第三行是公主的 q + 1 個不同格子編號。編號皆介於 1 到 n^2，路徑起點為 1，終點為 n^2。

輸出格式

每筆輸出 Case k: L，k 從 1 開始，L 為最長共同路徑的格子數。

題目來源：UVa 10635 — Prince and Princess。 原題：https://onlinejudge.org/external/106/10635.pdf