Palindromic Subsequence
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std; struct Node
{
int len;
string str;
}dp[][]; int main()
{
int l;
char str1[],str2[];
int i,j,k;
while(scanf("%s",str1+)!=EOF)
{
l=strlen(str1+);
for(i=;i<=l;i++)
str2[i]=str1[l-i+]; for(i=;i<=l;i++)
dp[][i].len=,dp[i][].len=,dp[][i].str="",dp[i][].str=""; for(i=;i<=l;i++)
{
for(j=;j<=l;j++)
{
if(str1[i]==str2[j])
{
dp[i][j].len=dp[i-][j-].len+;
dp[i][j].str=dp[i-][j-].str+str1[i];
}
else
{
if(dp[i][j-].len>dp[i-][j].len)
{
dp[i][j].len=dp[i][j-].len;
dp[i][j].str=dp[i][j-].str;
}
else if(dp[i-][j].len>dp[i][j-].len)
{
dp[i][j].len=dp[i-][j].len;
dp[i][j].str=dp[i-][j].str;
}
else
{
dp[i][j].len=dp[i-][j].len;
dp[i][j].str=min(dp[i-][j].str,dp[i][j-].str);
}
}
}
} int n=dp[l][l].len;
string ans=dp[l][l].str; if(n%==)
{
for(i=;i<n/;i++)
{
printf("%c",ans[i]);
}
for(i=n/-;i>=;i--)
{
printf("%c",ans[i]);
}
}
else
{
for(i=;i<n/;i++)
{
printf("%c",ans[i]);
}
for(i=n/;i>=;i--)
{
printf("%c",ans[i]);
}
}
printf("\n");
}
return ;
}