P3815 [FJOI2017] Palindromic Subsequence Problem

Let X and Y be two given sequences of positive integers $X=( x_1 , x_2 ,\cdots, x_m )$ and $Y=( y_1, y_2 ,\cdots, y_n )$. A common subsequence of X and Y is a sequence $(x_{i1}=y_{j1},x_{i2}=y_{j2},\cdots,x_{it}=y_{jt})$, where $i1

The file contains multiple test cases ($ \le 10$). For each test case, the first line contains a positive integer $n$ ($1\le n\le 500$), indicating that the lengths of the two input sequences X and Y are both $n$. The next two lines give the input sequences $X=(x_1,x_2,\cdots,x_n)$ and $Y=(y_1,y_2,\cdots, y_n)$, respectively. Each element in the sequences is a positive integer ($ \le 20000$). The file ends with a 0.

For each test case, output the computed length of the longest common palindromic subsequence, one length per line.

Translated by ChatGPT 5