UVa 10453 Make Palindrome(Simple DP)
6569 단어 Make
최소한 몇 개의 문자를 삽입해서 회문 문자열로 만들고 출력하는지 문자열을 지정합니다.
생각:
제목은 이미 사공이 익숙해졌는데, 회문열에 대한 출력은 틀림없이 귀속이다.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
char str[MAXN];
int dp[MAXN][MAXN];
void output(int i, int j)
{
if (i == j)
printf("%c", str[i]);
else if (str[i] == str[j])
{
printf("%c", str[i]);
if (i + 1 <= j - 1)
output(i + 1, j - 1);
printf("%c", str[j]);
}
else
{
if (dp[i+1][j] < dp[i][j-1])
{
printf("%c", str[i]);
output(i + 1, j);
printf("%c", str[i]);
}
else
{
printf("%c", str[j]);
output(i, j - 1);
printf("%c", str[j]);
}
}
}
int main()
{
while (scanf("%s", str) != EOF)
{
int n = strlen(str);
for (int i = 0; i < n; ++i)
{
dp[i][i] = 0;
if (str[i] == str[i+1])
dp[i][i+1] = 0;
else
dp[i][i+1] = 1;
}
for (int p = 2; p < n; ++p)
{
for (int i = 0, j = p; j < n; ++i, ++j)
{
if (str[i] == str[j])
dp[i][j] = dp[i+1][j-1];
else
dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;
}
}
printf("%d ", dp[0][n-1]);
output(0, n - 1);
printf("
");
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Windows용 GNU Make에서 PowerShell을 사용하는 방법Windows용 GNU Make를 설치하고 기본 설정으로 실행하면 쉘이 명령 프롬프트(cmd.exe)로 실행됩니다. 어떻게 해서 Windows PowerShell (powershell.exe)로 변경할 수 없는지 조...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
