题解：CF335B Palindrome
longlong_int
·
·
题解
DP 部分
状态
用 dp_{l, r} 表示 [l,r] 这个区间内最长回文子序列的长度。
转移
若 s_l=s_r，则 [l,r] 这个区间必定可以由 [l,l]、[l+1,r-1]、[r,r] 这三个区间拼接而来，且拼接完成后的子序列必定也是回文串。
否则，易得 dp_{l,r}=\max(dp_{l+1,r},dp_{l,r-1})。
所以，综合状态转移方程为：
dp_{l+1,r-1}+2 \operatorname{if}s_l = s_r\\
\max(dp_{l+1,r},dp_{l,r-1}) \operatorname{if}s_l \neq s_r
\end{cases}
DFS 部分
传参
DFS 传参：l,r,c，表示在 [l,r] 这个区间内找到一个长度为 c 的回文子序列并输出。
出口
## 递归
当 $s_l = s_r$ 时，在 $[l+1,r-1]$ 这个区间内找到一个长度为 $c-2$ 的回文子序列即可（$[l,l]$、$[l+1,r-1]$，$[r,r]$ 三个区间合并）
否则，先判断最长子序列在 $[l,r-1]$ 还是在 $[l+1,r]$ 内，再递归调用 `dfs(l, r - 1, c)` 或 `dfs(l + 1, r, c)` 即可。
# 后期处理
阅读到这里的你应该已经有了思路，准备切换到 ~~AC CODE~~ IDE 写代码了。但是先别急，上面思路的时间和空间复杂度均为 $\mathcal{O}(n^2)$，在 $n=5 \times 10^4$ 时不能通过。
由于题目描述中说 $s$ 只包含小写字母，也就是在 $|s| \geq 2600$ 时至少有一个字母出现了 $100$ 次及以上，则直接输出这个字母 $100$ 次即可。
# AC CODE & [Record](https://codeforces.com/problemset/submission/335/306313441)
```cpp
#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
inline ll read()
{
ll f = 1, sum = 0; char c = getchar();
while (!(48 <= c && c <= 57)) { if (c == '-') f = -1; c = getchar();}
while (48 <= c && c <= 57){sum = sum * 10 + c - 48; c = getchar();}
return sum * f;
}
inline void write(ll x)
{
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10); putchar(x % 10 + 48);
}
string s;
int dp[2620][2620];
void dfs(int l, int r, int cnt)
{
if (cnt == 0) return;
if (cnt == 1)
{
cout << s[l];
return;
}
if (s[l] == s[r])
{
cout << s[l];
dfs(l + 1, r - 1, cnt - 2);
cout << s[r];
}
else
{
if (dp[l][r] == dp[l + 1][r])
{
dfs(l + 1, r, cnt);
}
else
{
dfs(l, r - 1, cnt);
}
}
return;
}
map<char, int> mp;
int main()
{
cin >> s;
if ((int)(s.size()) >= 2600)
{
for (char i : s) mp[i]++;
for (char i = 'a'; i <= 'z'; i++)
{
if (mp[i] >= 100)
{
for (int hnfduinhsnfhdu = 1; hnfduinhsnfhdu <= 100; hnfduinhsnfhdu++)
{
cout << i;
}
return 0;
}
}
}
else
{
int n = s.size();
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++)
{
for (int l = 0; l + len - 1 < n; l++)
{
int r = l + len - 1;
if (s[l] == s[r]) dp[l][r] = dp[l + 1][r - 1] + 2;
else dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
}
}
dfs(0, n - 1, min(dp[0][n - 1], 100));
}
return 0;
}
```