Start: 2024-04-09 00:00:00

金华联赛复盘

End: 2024-04-13 00:00:00
Now　 2026-03-21 12:35:22　 类型: IOI　 状态: Ended　

P2. 最长回文子序列
Description

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。


Input

一个字符串

Output

求其最长的回文子序列

Examples

Input

bbbab

Output

4

Input

cbbd

Output

2
Hint

解释：一个可能的最长回文子序列为 “bbbb” 。

s的长度小于2000

Submit

题目参数
Time Limit 1 second
Memory Limit 128 MB
Submit