Reversed LCS [AtCoder Grand Contest 021 D] - はまやんはまやんはまやん

https://agc021.contest.atcoder.jp/tasks/agc021_d

前提知識

区間DP

解法

https://agc021.contest.atcoder.jp/submissions/2134939

まず、問題を以下のように言い換える。
「文字列SからK文字を入れ替えて作れる部分列の回文の最大長は？」
これは区間DPをすることで計算できる。
f(l,r,k) := Sの[l,r]の区間でk文字以内の入れ替えで作れる部分列の回文の最大値
遷移は関数f内を見るといい。
メモ化再帰でO(N^3)
　
問題はどうやってこの言い換えを思いつくかであるが、自分は思いつかないのでネットを駆け回って探した証拠的な物を以下に乗せておく

解説放送
公式解説
実は逆問題っぽいのがある
- AOJ It Prefokery Pio
- 解説
TとT'の逆のLCSと回文は関係性があることを覚えておくしか無い？（本番作れるか？）

string S; int K;
//---------------------------------------------------------------------------------------------------
int memo[303][303][303];
int f(int l, int r, int k) {
    if (memo[l][r][k]) return memo[l][r][k];
 
    int res = 0;
    if (l == r) res = 1;
    else if (l + 1 == r) {
        if (S[l] == S[r] or 0 < k) res = 2;
        else res = 1;
    } else {
        chmax(res, f(l + 1, r, k));
        chmax(res, f(l, r - 1, k));
        
        if (S[l] == S[r]) chmax(res, f(l + 1, r - 1, k) + 2);
        else if (0 < k) chmax(res, f(l + 1, r - 1, k - 1) + 2);
    }
 
    return memo[l][r][k] = res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> K;
    int N = S.length();
 
    cout << f(0, N - 1, K) << endl;
}