本来用区间DP,3次方的复杂度,T了,看了看题解,降维,直接二次方的复杂度可以解。然后折腾一下输出路径。。终于过了。
#include <cstring>
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
char str[];
int dp[][];
int p[];
int pre[];
int flag[];
int main()
{
int i,len,j;
scanf("%s",str);
len = strlen(str);
for(i = ; i <= len; i ++)
{
dp[i][i] = ;
for(j = ;; j ++)
{
if(i-j+ < )break;
if(i+j >= len) break;
if(str[i-j] != str[i+j]) break;
dp[i-j][i+j] = ;
}
for(j = ;; j ++)
{
if(i-j+ < )break;
if(i+j >= len) break;
if(str[i-j+] != str[i+j]) break;
dp[i-j+][i+j] = ;
}
}
for(i = ; i < len; i ++)
p[i] = ;
p[] = ;
for(i = ; i < len; i ++)
{
if(dp[][i])
{
pre[i] = ;
p[i] = ;
}
}
for(i = ; i < len; i ++)
{
if(p[i] == ) continue;
for(j = ; j < i; j ++)
{
if(dp[j+][i])
{
if(p[i] > p[j] + )
{
pre[i] = j+;
p[i] = p[j]+;
}
}
}
}
printf("%d\n",p[len-]);
int a = pre[len-];
if(a != )
flag[a] = ;
a --;
while(p[len-] >= )
{
a = pre[a];
if(a != )
flag[a] = ;
a --;
p[len-] --;
}
for(i = ; i < len; i ++)
{
if(flag[i]) printf(" ");
printf("%c",str[i]);
}
printf("\n");
return ;
}