分数: 900 点
问题陈述
高桥决定送一根绳子给他的母亲。
的 值 字符串的 一个字符串的 T 是最长公共子序列的长度 T 和 T',其中 T' 是反转得到的字符串 T。 也就是说,该值是以下两个相等的字符串中最长的长度: T (可能不连续),以及子序列 T' (可能不连续)。
高桥有一根绳子 S。他想给她妈妈一个尽可能高的值的字符串,所以他最多想改变 K 中的字符 S 到任何其他字符以获得可能的最高值的字符串。 找到可实现的最高可能价值。
约束
- 1 \leq |S| \leq 300
- 0 \leq K \leq |S|
- S 由小写英文字母组成。
- K 是一个整数。
输入
输入由标准输入按以下格式给出:
S K
输出
打印可实现的最高可能值。
示例输入 1
abcabcabc 1
示例输出 1
7
将第一个字符更改为 c 结果 cbcabcabc。
让这个字符串成为 T,那么一个最长公共子序列 T 和 T' is cbabcbc,其长度为 7.
示例输入 2
atcodergrandcontest 3
示例输出 2
15