800 . 最長迴文子序列

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

huangallen
🔥🐥

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

16.1% (5/31)

Tags

apcsc apcsc-dp

Description

小 B 最近在學習字串相關的演算法，他對迴文字串相當有興趣，對於一個字串 $S$，他想要找到其子序列 $T$ 並讓它是一個迴文，除此之外，他還希望這個子序列 $T$ 越長越好，但太長的字串會讓小 B 頭昏眼花，所以當答案長度超過 $1000$ 的時候你可以直接輸出一個長度只有 $1000$ 的迴文子序列來唬爛小 B，當然更長的序列也沒有問題。

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

Input Format

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

  • $|S| \leq 200000$

Output Format

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

Sample Input 1

123456

Sample Output 1

6

Sample Input 2

715234317

Sample Output 2

7134317

Hints

Problem Source

TIOJ 2061

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~38 $|S| \leq 1000$ 40
3 0~83 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2 3
1 3000 524288 65536 1 2 3
2 3000 524288 65536 2 3
3 3000 524288 65536 2 3
4 3000 524288 65536 2 3
5 3000 524288 65536 2 3
6 3000 524288 65536 2 3
7 3000 524288 65536 2 3
8 3000 524288 65536 2 3
9 3000 524288 65536 2 3
10 3000 524288 65536 2 3
11 3000 524288 65536 2 3
12 3000 524288 65536 2 3
13 3000 524288 65536 2 3
14 3000 524288 65536 2 3
15 3000 524288 65536 2 3
16 3000 524288 65536 2 3
17 3000 524288 65536 2 3
18 3000 524288 65536 2 3
19 3000 524288 65536 2 3
20 3000 524288 65536 2 3
21 3000 524288 65536 2 3
22 3000 524288 65536 2 3
23 3000 524288 65536 2 3
24 3000 524288 65536 2 3
25 3000 524288 65536 2 3
26 3000 524288 65536 2 3
27 3000 524288 65536 2 3
28 3000 524288 65536 2 3
29 3000 524288 65536 2 3
30 3000 524288 65536 2 3
31 3000 524288 65536 2 3
32 3000 524288 65536 2 3
33 3000 524288 65536 2 3
34 3000 524288 65536 2 3
35 3000 524288 65536 2 3
36 3000 524288 65536 2 3
37 3000 524288 65536 2 3
38 3000 524288 65536 2 3
39 3000 524288 65536 3
40 3000 524288 65536 3
41 3000 524288 65536 3
42 3000 524288 65536 3
43 3000 524288 65536 3
44 3000 524288 65536 3
45 3000 524288 65536 3
46 3000 524288 65536 3
47 3000 524288 65536 3
48 3000 524288 65536 3
49 3000 524288 65536 3
50 3000 524288 65536 3
51 3000 524288 65536 3
52 3000 524288 65536 3
53 3000 524288 65536 3
54 3000 524288 65536 3
55 3000 524288 65536 3
56 3000 524288 65536 3
57 3000 524288 65536 3
58 3000 524288 65536 3
59 3000 524288 65536 3
60 3000 524288 65536 3
61 3000 524288 65536 3
62 3000 524288 65536 3
63 3000 524288 65536 3
64 3000 524288 65536 3
65 3000 524288 65536 3
66 3000 524288 65536 3
67 3000 524288 65536 3
68 3000 524288 65536 3
69 3000 524288 65536 3
70 3000 524288 65536 3
71 3000 524288 65536 3
72 3000 524288 65536 3
73 3000 524288 65536 3
74 3000 524288 65536 3
75 3000 524288 65536 3
76 3000 524288 65536 3
77 3000 524288 65536 3
78 3000 524288 65536 3
79 3000 524288 65536 3
80 3000 524288 65536 3
81 3000 524288 65536 3
82 3000 524288 65536 3
83 3000 524288 65536 3
Submit
Back to Top