2061 . 最長回文子序列（LPS）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
$\Huge\text{pooh is 8}$

User's AC Ratio

62.9% (66/105)

Submission's AC Ratio

18.7% (136/727)

Tags

CKcon 2018-CKcon

Description

給定一字串$S$，請找出它的所有回文子序列中最長的一個。如果有很多個，那只要隨便輸出一個就好了。

一個字串是「回文」代表它倒過來和原本的字串一樣。
一個字串的子序列的是把它其中一些字元刪去所得到的新字串（可以不刪去任何字元），例如3、123、293、11293都是11293的子序列。

Input Format

輸入只有一行，為一個只由數字字元（0到9）組成的字串$S$。

Output Format

請輸出$S$中任意一個長度至少$\min(1000, P)$的回文子序列，其中$P$是$S$的最長回文子序列的長度。

Sample Input 1

123456

Sample Output 1

1

Hints

Problem Source

Problem set by edisonhello
建國中學107學年度校隊選拔：初試pC

Subtasks

No. Testdata Range Constraints Score
1 0~9 $\lvert S \rvert \leq 20$ 12
2 0~19 $\lvert S \rvert \leq 87$ 9
3 0~29 $\lvert S \rvert \leq 300$ 13
4 0~49 $\lvert S \rvert \leq 1000$ 37
5 0~64 $\lvert S \rvert \leq 200000$ 29

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 524288 262144 1 2 3 4 5
1 900 524288 262144 1 2 3 4 5
2 900 524288 262144 1 2 3 4 5
3 900 524288 262144 1 2 3 4 5
4 900 524288 262144 1 2 3 4 5
5 900 524288 262144 1 2 3 4 5
6 900 524288 262144 1 2 3 4 5
7 900 524288 262144 1 2 3 4 5
8 900 524288 262144 1 2 3 4 5
9 900 524288 262144 1 2 3 4 5
10 900 524288 262144 2 3 4 5
11 900 524288 262144 2 3 4 5
12 900 524288 262144 2 3 4 5
13 900 524288 262144 2 3 4 5
14 900 524288 262144 2 3 4 5
15 900 524288 262144 2 3 4 5
16 900 524288 262144 2 3 4 5
17 900 524288 262144 2 3 4 5
18 900 524288 262144 2 3 4 5
19 900 524288 262144 2 3 4 5
20 900 524288 262144 3 4 5
21 900 524288 262144 3 4 5
22 900 524288 262144 3 4 5
23 900 524288 262144 3 4 5
24 900 524288 262144 3 4 5
25 900 524288 262144 3 4 5
26 900 524288 262144 3 4 5
27 900 524288 262144 3 4 5
28 900 524288 262144 3 4 5
29 900 524288 262144 3 4 5
30 900 524288 262144 4 5
31 900 524288 262144 4 5
32 900 524288 262144 4 5
33 900 524288 262144 4 5
34 900 524288 262144 4 5
35 900 524288 262144 4 5
36 900 524288 262144 4 5
37 900 524288 262144 4 5
38 900 524288 262144 4 5
39 900 524288 262144 4 5
40 900 524288 262144 4 5
41 900 524288 262144 4 5
42 900 524288 262144 4 5
43 900 524288 262144 4 5
44 900 524288 262144 4 5
45 900 524288 262144 4 5
46 900 524288 262144 4 5
47 900 524288 262144 4 5
48 900 524288 262144 4 5
49 900 524288 262144 4 5
50 1900 524288 262144 5
51 1900 524288 262144 5
52 1900 524288 262144 5
53 1900 524288 262144 5
54 1900 524288 262144 5
55 1900 524288 262144 5
56 1900 524288 262144 5
57 1900 524288 262144 5
58 1900 524288 262144 5
59 1900 524288 262144 5
60 1900 524288 262144 5
61 1900 524288 262144 5
62 1900 524288 262144 5
63 1900 524288 262144 5
64 1900 524288 262144 5
Submit
Back to Top