#B4336. [中山市赛 2023] 永别

    ID: 14217 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>动态规划 DP2023广东科创活动小学活动

[中山市赛 2023] 永别

题目描述

你做了一个梦,梦里有一个字符串,这个字符串无论正着读还是倒着读都是一样的,例如:abcba\tt abcba 就符合这个条件。

但是你醒来时不记得梦中的字符串是什么,只记得它是另一个字符串 SS 的子序列,你想知道梦中字符串最长是多少。

提示:字符串 AA 是字符串 BB 的子序列当且仅当从 BB 中删除若干个字符(可以不删)后可以变成 AA。例如:acd\tt acdachda\tt achda 的子序列,因为从 achda\tt achda 中删去第 33 个和第 55 个字符后就是 acd\tt acd

输入格式

第一行一个正整数 lenlen,表示字符串 SS 的长度。

第二行一个长度为 lenlen 的字符串,表示字符串 SS

输出格式

第一行包含一个整数,表示梦中字符串最长的长度。

7
acbdcaa
5

提示

样例解释

acbdcaa\tt acbdcaa 中删去第 44 个和第 77 个字符后变成 acbca\tt acbca 就满足正着读还是倒着读都是一样,不难发 现这是最长的。

数据范围

对于 15%15\% 的数据,len20len \le 20

对于 30%30\% 的数据,len200len \le 200

对于 45%45\% 的数据,len700len \le 700

对于另外 15%15\% 的数据,len800len \le 800,字符串中只会出现字母 a\tt ab\tt b

对于 100%100\% 的数据,3len10003 \le len \le 1000,字符串中只会出现英文小写字母。