10453 - Make Palindrome

[cpp] 
描述：把一個字符串通過增加操作變成回文，然後把這個回文輸出 
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
char str[1010]; 
int p[1010][1010]; 
int v[1010][1010]; 
int min(int x,int y) 
{ 
    return x>y?y:x; 
} 
int dp(int x,int y) 
{ 
    if(v[x][y]!=-1) return v[x][y]; 
    if(x>=y) return v[x][y]=0; 
    if(str[x]==str[y]) 
    { 
        p[x][y]=1; 
        v[x][y]=dp(x+1,y-1); 
    } 
    else 
    { 
        int a=dp(x+1,y); 
        int b=dp(x,y-1); 
        if(a>b) p[x][y]=2; 
        else p[x][y]=3; 
        v[x][y]=min(a,b)+1; 
    } 
    return v[x][y]; 
} 
void show(int x,int y) 
{ 
    if(x>y) return; 
    if(x==y) printf("%c",str[x]); 
    if(p[x][y]==1) 
    { 
        printf("%c",str[x]); 
        show(x+1,y-1); 
        printf("%c",str[y]); 
    } 
    else if(p[x][y]==2) 
    { 
        printf("%c",str[y]); 
        show(x,y-1); 
        printf("%c",str[y]); 
    } 
    else if(p[x][y]==3) 
    { 
        printf("%c",str[x]); 
        show(x+1,y); 
        printf("%c",str[x]); 
    } 
} 
int main() 
{ 
   // freopen("a.txt","r",stdin);  
    while(gets(str)) 
    { 
        int len=strlen(str); 
        memset(v,-1,sizeof(v)); 
        memset(p,0,sizeof(p)); 
        printf("%d ",dp(0,len-1)); 
        show(0,len-1); 
        puts(""); 
    } 
    return 0; 
}