uva 10453 Make Palindrome

本文主要是介绍uva 10453 Make Palindrome，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你n个串（长度最多为1000)，问对于每个串插入最少多少m个字符能使它变成一个回文串。输出m，并把回文串输出.

看了解题报告。总结，还要随便用memset，否则会T。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1005;
struct node
{int cost,cmd;int x,y;void fz(int b,int c,int d){cmd=b;x=c;y=d;}
}map[N][N];
int le,ri;
char L[N],R[N],str[N];
int fun(int,int );
int print_ans(int,int);
int main()
{while(gets(str+1)){le=0;ri=0;int len=strlen(str+1);printf("%d ",fun(1,len));print_ans(1,len);L[le]='\0';printf("%s",L);for(int i=ri-1;i>=0;i--) putchar(R[i]);puts("");for(int i=0;i<=len;i++){for(int j=0;j<=len;j++){map[i][j].cost=0;}}}return 0;
}
int fun(int x,int y)
{if(x>=y){return 0;}else if(map[x][y].cost) return map[x][y].cost;else{if(str[x]==str[y]){map[x][y].cost=fun(x+1,y-1);map[x][y].fz(3,x+1,y-1);}else{int temp1=fun(x,y-1)+1,temp2=fun(x+1,y)+1;if(temp1>temp2){map[x][y].cost=temp2;map[x][y].fz(2,x+1,y);}else{map[x][y].cost=temp1;map[x][y].fz(1,x,y-1);}}return map[x][y].cost;}
}
int print_ans(int x,int y)
{if(x==y){L[le++]=str[x];return 1;}if(map[x][y].cmd==1){L[le++]=str[y];R[ri++]=str[y];}else if(map[x][y].cmd==2){L[le++]=str[x];R[ri++]=str[x];}else if(map[x][y].cmd==3){L[le++]=str[y];R[ri++]=str[y];if(x==y-1)return 1;}if(print_ans(map[x][y].x,map[x][y].y)) return 1;return 0;
}

这篇关于uva 10453 Make Palindrome的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---