AT_agc021_d [AGC021D] Reversed LCS

[problemUrl]: https://atcoder.jp/contests/agc021/tasks/agc021_d 高橋君はお母さんに文字列をプレゼントすることにしました。 文字列 $ T $ の価値とは、$ T $ を逆から読んだものを $ T' $ として、$ T $ と $ T' $ の最長共通部分列の長さです。 すなわち、(連続するとは限らない)部分列として $ T $ と $ T' $ の両方に現れるものの最大長です。 高橋君は、文字列 $ S $ を持っています。お母さんにできるだけ価値の高い文字列をプレゼントしたい高橋君は、 $ S $ の文字を $ K $ 箇所まで任意に変更して、できるだけ価値の高い文字列を作りたいです。 達成できる価値の最大値を求めてください。

N/A

N/A

### 制約 - $ 1\ \leq\ |S|\ \leq\ 300 $ - $ 0\ \leq\ K\ \leq\ |S| $ - $ S $ は英小文字からなる - $ K $ は整数である ### Sample Explanation 1 $ 1 $ 文字目を `c` に変更すると、文字列は `cbcabcabc` になります。 できた文字列を $ T $ とおけば、長さ $ 7 $ の文字列 `cbabcbc` が $ T $ と $ T' $ の最長共通部分列の一例となります。