Solution - Atcoder AGC021D Reversed LCS

考虑到 \(\operatorname{LCS}(T, T')\) 这个形式实在是不太优美，考虑转化一下形式。
感受一下，能够知道 \(T\) 的最长回文子序列 \(|\operatorname{LPS}(T)| = |\operatorname{LCS}(T, T')|\)。
具体证明可以见 zhihu，本人暂时还没看懂。

那么接下来对于单个串的 \(\operatorname{LPS}\) 就相对好求了。
考虑区间 DP，设 \(f_{l, r, k}\) 为此时处理到了前 \(l\) 个和第 \(r\) 个及之后，还能换 \(k\) 次的最优解。
那么转移就考虑两种情况：

1. 不让 \(l, r\) 产生贡献，即 \(f_{l, r, k} \leftarrow \max\{f_{l + 1, r, k}, f_{l, r - 1, k}\}\)。
2. 让 \(l, r\) 产生贡献，即 \(f_{l, r, k}\leftarrow f_{l + 1, r - 1, k - [s_l\not = s_r]} + 2\)。
   特殊的，有 \(f_{l, r, k} = -\infty(k < 0),f_{l, l, k} = 1\)。

时间复杂度 \(\mathcal{O}(|s|^3)\)。

#include<bits/stdc++.h>
const int maxn = 3e2 + 10;
char s[maxn];
int f[maxn][maxn][maxn], vis[maxn][maxn][maxn];
int calc(int l, int r, int k) {
   if (k < 0) return -1e9;
   if (l >= r) return l == r;
   if (vis[l][r][k]++) return f[l][r][k];
   return f[l][r][k] = std::max({calc(l + 1, r, k), calc(l, r - 1, k), calc(l + 1, r - 1, k - (s[l] != s[r])) + 2});
}
int main() {
   int k;
   scanf("%s%d", s + 1, &k);
   printf("%d\n", calc(1, strlen(s + 1), k));
   return 0;
}