Make Palindrome
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; char str[];
int dp[][],react[][]; int dfs(int x,int y)
{
if(x>y)
return ;
if(x==y)
printf("%c",str[x]);
else if(react[x][y]==)
{
printf("%c",str[x]);
dfs(x+,y-);
printf("%c",str[y]);
}
else if(react[x][y]==)
{
printf("%c",str[y]);
dfs(x,y-);
printf("%C",str[y]);
}
else if(react[x][y]==)
{
printf("%c",str[x]);
dfs(x+,y);
printf("%c",str[x]);
}
return ;
} int main()
{
int n;
int i,j,k;
while(scanf("%s",str)!=EOF)
{
memset(dp,,sizeof(dp));
memset(react,,sizeof(react)); n=strlen(str);
for(i=n-;i>=;i--)
{
for(j=i+;j<n;j++)
{
if(str[i]==str[j])
{
dp[i][j]=dp[i+][j-];
}
else
{
if(dp[i+][j]>dp[i][j-])
{
dp[i][j]=dp[i][j-]+;
react[i][j]=;
}
else
{
dp[i][j]=dp[i+][j]+;
react[i][j]=;
}
}
}
} printf("%d ",dp[][n-]);
dfs(,n-);
printf("\n");
}
return ;
}