Palindrome

5318 단어
질문 설명: 문자열을 하나 드리겠습니다. 최소한 몇 개의 문자를 추가해야만 답장열을 만들 수 있습니다.
in:
5Ab3bd
out:
2
설명: dAb3bAd
방법: 주어진 문자열을 반대로 한 번 저장한 다음 가장 긴 공통 서열을 찾아서 원래 길이에서 이 길이를 빼면 추가해야 할 문자 수입니다
길이 n이 [35000]이기 때문이다.5000개의 2차원 그룹 회의 mle를 열기 때문에 우리는 스크롤 그룹을 사용합니다. 상태 이동 방정식이 우리에게 알려주기 때문에
만약 a[i]==b[j]라면 dp[i][j]=dp[i-1][j-1]+1
하면, 만약, 만약...b[j]는 dp[i][j]=max(dp[i-1][j], dp[i][j-1])
dp[i][j]의 상태는 서로 인접한 두 줄 사이에서만 이동할 수 있기 때문에 스크롤 그룹의 유효성을 보장합니다. 그런데 여기도 이상한 점이 하나 있습니다. 만약에 std::string 메모리 문자열을 사용하면 RE를 할 수 있습니다. 계속 이해하지 못했습니다. 지나가는 아저씨가 조언해 주세요.
if(a[i]==b[j])
dp[(i+1)%2][j+1]=dp[i%2][j]+1;
else
dp[(i+1)%2][j+1]=max(dp[i%2][j+1],dp[(i+1)%2][j]);

전체 코드:
#include
#include<string.h>
#include
#include<string>
#include
using namespace std;
char a[5050],b[5050];
int dp[2][5020];
int main()
{
    int n,i,j;
    while(~scanf("%d",&n))
    {
        j=0;
        //cin>>a;
        scanf("%s",&a);
        for(i=0; i)
            b[j++]=a[n-1-i];
        for(i=0;i)
        {
            for(j=0;j)
             {
               if(a[i]==b[j])
                dp[(i+1)%2][j+1]=dp[i%2][j]+1;
               else
                dp[(i+1)%2][j+1]=max(dp[i%2][j+1],dp[(i+1)%2][j]);
             }
        }
        printf("%d
",n-dp[n%2][n]); //a.clear(); //b.clear(); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(dp,0,sizeof(dp)); } return 0; }

 

좋은 웹페이지 즐겨찾기