2 seconds
256 megabytes
standard input
standard output
Given a string s, determine if it contains any palindrome of length exactly 100 as
a subsequence. If it has any, print any one of them. If it doesn't have any, print a palindrome that is a subsequence of s and
is as long as possible.
The only line of the input contains one string s of length n (1 ≤ n ≤ 5·104)
containing only lowercase English letters.
If s contains a palindrome of length exactly 100 as a subsequence,
print any palindrome of length 100 which is a subsequence of s.
If sdoesn't contain any palindromes of length exactly 100,
print a palindrome that is a subsequence of s and is as long as possible.
If there exists multiple answers, you are allowed to print any of them.
bbbabcbbb
bbbcbbb
rquwmzexectvnbanemsmdufrg
rumenanemur
代码：
#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAXN 111111
char s[MAXN];
int N = 0;
#define MAXM 111
int dp[MAXN][111], prefi[MAXN][111], prefj[MAXN][111];
int last[MAXN][MAXM];
int best = 0;
char tmp[MAXN];
char ans[MAXN];
int main() {
scanf("%s", s);
N = strlen(s);
for (int i = 0; i < 26; i ++)
last[0][i] = -1;
for (int i = 0; i < N; i ++) {
for (int j = 0; j < 26; j ++) {
last[i + 1][j] = last[i][j];
last[i + 1][s[i] - 'a'] = i;
}
}
for (int j = 0; j < MAXN; j ++) {
dp[0][j] = -1;
}
dp[0][0] = N;
for (int i = 0; i < N; i ++)
for (int j = 0; j < 55; j ++)
if (dp[i][j] >= i) {
int len = 2 * j + (dp[i][j] > i);
if(len <= 100 && best < len) {
best = len;
int ii = i, jj = j;
int n = 0;
while(jj) {
int ni = prefi[ii][jj], nj = prefj[ii][jj];
if (nj != jj) tmp[n++] = s[ni];
ii = ni; jj = nj;
}
int A = 0;
for (int k = 0; k < n; k ++)
ans[A++] = tmp[n - 1 - k];
if (dp[i][j] > i) ans[A++] = s[i];
for (int k = 0; k < n; k ++)
ans[A++] = tmp[k];
}
if(dp[i][j] > dp[i+1][j]) {
prefi[i+1][j] = i; prefj[i+1][j] = j;
dp[i+1][j] = dp[i][j];
}
if(last[dp[i][j]][s[i]-'a'] > dp[i+1][j+1]) {
prefi[i+1][j+1] = i; prefj[i+1][j+1] = j;
dp[i+1][j+1] = last[dp[i][j]][s[i]-'a'];
}
}
ans[best] = '\0';
printf("%s\n", ans);
return 0;
}