5693: 最长回文子序列

srf切完题后喜欢玩游戏。他喜欢找qty玩将军棋。
但是今天qty去ak IOI了，没有来，他只好自己一个人玩字符串。
当然，他不会认为所有的字符串都好玩。
他定义一个字符串S的子序列T为从S中按顺序挑出一些字母组成的非空字符串，但是不一定连续。（即设wi为Ti在S中的位置，对于任意i!=j，有wi!=wj；对于任意i<j，有wi<wj。）
他认为一个字符串，他的好玩程度为其最长的回文子序列的长度。
他想知道自己随手写出的一个字符串的好玩程度是什么，来决定是不是要玩这个字符串。
但是他刚刚切完题，太累了，就决定把这个问题交给你来解决。

abrtycduiocwqb

5

可以观察发现，最长的回文子序列为bcdcb
区间dp