UVA 11404 Palindromic Subsequence(문자 DP 제거, 레벨 4)
Crawling in process...
Crawling failed
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
Submit
Status
Appoint description: System Crawler (2013-05-30) acmparand (2013-08-02)
Description
A Subsequence is a sequence obtained by deleting zero or more characters in a string. A Palindrome is a string which when read from left to right, reads same as when read from right to left. Given a string, find the longest palindromic subsequence. If there are many answers to it, print the one that comes lexicographically earliest.
Constraints
Input
Input consists of several strings, each in a separate line. Input is terminated by EOF.
Output
For each line in the input, print the output in a single line.
Sample Input
aabbaabb
computer
abzla
samhita
Sample Output
aabbaa
c
aba
aha
, 。 string
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define clr(f,z) memset(f,z,sizeof(f))
using namespace std;
const int mm=1005;
char s[mm],rs[mm];
class Node
{
public:
int len;string s;
bool operator<(const Node&x)const
{
if(len!=x.len)return len<x.len;
return s>x.s;
}
}dp[mm][mm];
void LCS(int len)
{
FOR(i,0,len)
{
dp[i][0].len=0;dp[i][0].s.clear();
dp[0][i].len=0;dp[0][i].s.clear();
}
FOR(i,1,len)FOR(j,1,len)
{
if(s[i]==rs[j])//lcs
{
dp[i][j].len=dp[i-1][j-1].len+1;
dp[i][j].s=dp[i-1][j-1].s+s[i];
}
else
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
string revrse(string s)
{
string tmp="";
for(int i=s.length()-1;i>=0;--i)
tmp+=s[i];
return tmp;
}
string getans(int len)
{
Node ans;
ans.s.clear();ans.len=0;
FOR(i,1,len-1)
{
ans=max(ans,dp[i][len-i]);
}
ans.len+=ans.len;
ans.s+=revrse(ans.s);
Node tmp;
FOR(i,1,len)
{ tmp.len=2*dp[i-1][len-i].len+1;
tmp.s=dp[i-1][len-i].s+s[i]+revrse(dp[i-1][len-i].s);
ans=max(ans,tmp);
}
return ans.s;
}
int main()
{
while(cin>>s+1)
{int len=strlen(s+1);
FOR(i,1,len)rs[i]=s[len-i+1];
LCS(len);
cout<<getans(len)<<"
";
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.