UVa 10453 - Make Palindrome 문자열 dp
Make Palindrome
Input: standard input
Output: standard output
Time Limit: 8 seconds
By definition palindrome is a string which is not changed when reversed. "MADAM"is a nice example of palindrome. It is an easy job to test whether a given string is a palindrome or not. But it may not be so easy to generate a palindrome.
Here we will make a palindrome generator which will take an input string and return a palindrome. You can easily verify that for a string of length 'n', no more than (n-1) characters are required to make it a palindrome. Consider "abcd"and its palindrome "abcdcba"or "abc"and its palindrome "abcba". But life is not so easy for programmers!! We always want optimal cost. And you have to find the minimum number of characters required to make a given string to a palindrome if you are allowed to insert characters at any position of the string.
Input
Each input line consists only of lower case letters. The size of input string will be at most 1000. Input is terminated by EOF.
Output
For each input print the minimum number of characters and such a palindrome seperated by one space in a line. There may be many such palindromes. Any one will be accepted.
Sample Input
abcdaaaaabcaababababaabababapqrsabcdpqrs
Sample Output
3 abcdcba0 aaaa2 abcba1 baab0 abababaabababa9 pqrsabcdpqrqpdcbasrqp
Author : Md. Kamruzzaman
The Real Programmers' Contest-2
-----------------------
f[i][j]=f[i+1][j-1]; (s[i]==s[j]) i==j일 때 문자를 추가할 필요가 없습니다
f[i][j]=min( f[i+1][j], f[i][j-1] )+1; 하다j시, 1. j 오른쪽에 s[i]를 추가하고, 2. i 왼쪽에 s[j]를 추가한다.
새로운 저장 dp 경로의 방식을 배웠다.
p[i][j]==0일 때 s[i]=s[j]의 상황을 나타낸다
p[i][j]==1은 상황 1을 나타낸다.p[i][j]==-1은 상황 2를 나타낸다.
-------------------------
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char s[1111];
int f[1111][1111];
int q[1111][1111];
int n;
int dfs(int l,int r)
{
if (r-l<1)
{
return 0;
}
if (f[l][r]!=-1)
{
return f[l][r];
}
int ret=0;
if (s[l]==s[r])
{
ret=dfs(l+1,r-1);
q[l][r]=0;
}
else
{
ret=dfs(l+1,r)+1;
q[l][r]=1;
if (dfs(l,r-1)+1<ret)
{
ret=dfs(l,r-1)+1;
q[l][r]=-1;
}
}
f[l][r]=ret;
return ret;
}
int main()
{
while (cin>>(s+1))
{
string str1,str2,str;
memset(f,-1,sizeof(f));
memset(q,0,sizeof(q));
n=strlen(s+1);
int ans=dfs(1,n);
int x=1,y=n;
while (y-x>=0)
{
if (q[x][y]==0)
{
if (x==y)
{
str1+=s[x];
x++;
y--;
}
else
{
str1+=s[x];
str2+=s[y];
x++;
y--;
}
}
else if (q[x][y]==1)
{
str1+=s[x];
str2+=s[x];
x++;
}
else if (q[x][y]==-1)
{
str1+=s[y];
str2+=s[y];
y--;
}
}
for (int i=str2.length()-1; i>=0; i--)
{
str1+=str2[i];
}
cout<<ans<<" "<<str1<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
49일차 - 2022.04.20Baekjoon에서 문제풀이 1) 문제 : 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제/ 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 첫째 줄부터 N번째 줄까지 차례대로 별...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.