1159:Palindrome

keyword

動的計画法　回文　C

概要

長さ5000以下の文字列が与えられる。このとき文字を最低いくつ削れば回文になるか求める問題。
今考えてる文字列の両端が等しい場合は両端を取り除いた文字列を考えれば良く、そうでないときは両方取り除いた場合やいずれか一方を取り除いた場合を考えれば良い。なのでメモ化して5000^2の計算量(時間、空間共に)で解ける。MLEとTLEを両方もらったので、intをshortに置き換えたり再帰呼び出しの回数を減らしたりして制限ギリギリで通った。多分もっと綺麗に解けると思う。

short memo[5001][5001];
char str[5002];

short rec(int from, int end){
    short t;
    if(from>=end) return 0;
    if(from+1==end) return memo[from][end]=(str[from]==str[end]?0:2);

    if(str[from] == str[end]){
        if(memo[from+1][end-1] < 1<<14)
            return memo[from][end] = memo[from+1][end-1];
        return memo[from][end] = rec(from+1,end-1);
    }

    if(memo[from+1][end]<1<<14) t = memo[from+1][end]+1;
    else t = rec(from+1,end) + 1;
    if(t < memo[from][end]) memo[from][end] = t;

    if(memo[from][end-1]<1<<14) t = memo[from][end-1]+1;
    else t = rec(from,end-1) + 1;
    if(t < memo[from][end]) memo[from][end] = t;

    if(memo[from+1][end-1]<1<<14) t = memo[from+1][end-1]+2;
    else t = rec(from+1,end-1)+2;
    if(t < memo[from][end]) memo[from][end] = t;

    return memo[from][end];
}

int main(){
    int n,i,j;
    scanf("%d\n",&n);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            memo[i][j]=1<<14;
    scanf("%s\n",str);
    printf("%d\n",(int)rec(0,n-1));
}