← 返回题目列表

AtCoder · agc021_d

D. 反向 LCS

中文机器翻译题面 查看原题

分数: 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