【POJ 1159】Palindrome

【POJ 1159】Palindrome
최근 각종 문제, 각종 진기한 사고방식은 이미 사공에서 흔히 볼 수 있는 것이다...또 하나의 스크롤 그룹 = = 이 문제는 최소한 보충해야 할 알파벳 수를 알아야 할 것이 하나 더 있다 = 원 서열 S의 길이 - S와 S의 가장 긴 공통 문자열 길이를 둥지는 원래 몰랐다. 그리고 괴상한 dp 방법이 LCS보다 0.0 빠르다는 것을 썼다
나의 사고방식은 왼쪽에서 오른쪽으로 모든 문자를 오른쪽에서 왼쪽으로 그의 뒷자리까지 dp수 그룹이 현재 위치에서 오른쪽으로 일치하는 문자열의 왼쪽 끝에 있는 가장 긴 서열 길이의 두 배(즉 서열 길이를 삭제하는 것)를 표시하는 것이다.str[i]==str[j]를 찾을 때마다 dp[j]를 업데이트하고 이를 위해 가장 긴 서열 +2(좌우 대칭)를 업데이트하는 것이다.Max가 가장 많이 저장된 좌우 대칭 같은 문자를 사용하여 n-Max를 출력합니다. 즉, 추가해야 할 문자를 위해 Max의 업데이트를 j에 주의해야 합니다!i+1 업데이트 시 Max = max (Max, dp[j]+1) 는 기회문 문자열 i~j 사이에 문자 '특권을 부여할 수 있기 때문입니다.
정상적인 스크롤 그룹 방법은 LCS와 같지만 MLE를 방지하기 위해 1차원을 01로 대체합니다. i를 반복할 때마다 i-2와 이전의 dp 그룹은 모두 사용하지 않기 때문에 비우는 것과 같습니다.
코드는 다음과 같습니다.

//    dp
#include <iostream>
#include <cstdio>
#define sz 5000

using namespace std;

int dp[2][sz+1];
char s1[sz+2],s2[sz+2];

int main()
{
    int n,i,j,e = 1;
    scanf("%d",&n);
    scanf("%s",s1+1);
    for(i = 1; i <= n; ++i)
    {
        s2[i] = s1[n-i+1];
    }
    dp[0][0] = 0;
    for(i = 1; i <= n; ++i,e^=1)//e 1 0 1 0     " "   
    {
        for(j = 1; j <= n; ++j)
        {
            if(s1[i] == s2[j]) dp[e][j] = dp[e^1][j-1]+1;
            else dp[e][j] = max(dp[e][j-1],dp[e^1][j]);
        }
    }
    printf("%d
",n-dp[e^1][n]);
    return 0;
}

//      
#include <iostream>
#include <cstdio>
#include <cstring>
#define INF 0x3f3f3f3f

using namespace std;

char str[5001];
int dp[5001];

int main()
{
    int n,i,j,cnt,mm,x;
    scanf("%d%s",&n,str);
    memset(dp,0,sizeof(dp));
    mm = 1;
    for(i = 0; i < n; ++i)
    {
        x = 0;
        cnt = 0;
        for(j = n-1; j > i; --j)
        {
            x = max(x,dp[j]);//           
            if(str[j] == str[i])
            {
                dp[j] = max(dp[j],cnt+2);//     cnt+2(      )
                if(j == i+1) mm = max(mm,dp[j]);
                else mm = max(mm,dp[j]+1);//      
            }
            cnt = x;//               
        }
    }
    printf("%d
",n-mm);
    return 0;
}