POJ 1159 Palindrome(LCS)

题目链接http://poj.org/problem?id=1159

题目大意:给定一串字符,添加最少的字符,使之成为回文串。

Sample Input

5
Ab3bd

Sample Output

2

分析:这道题目之前有做过,就是将原字符串逆序得到另一个字符串,求它们的最长公共子序列,这样就能求得它的可以构成回文的最长字符数,用n减去即为添加最少可使之成为回文的数目。

可恨的是之前一直超内存,看了别人的解题报告,原来定义dp[MAX][MAX]时,不用int型,而是short型,内存只占int的一半(见上一篇日志)

另外逆序字符串可以不用新开一个数组,也可以直接在原数组上从后往前循环。

代码如下:
 # include<stdio.h>
# include<string.h> #define MAX 5005 int max(int a,int b,int c){
int temp;
temp = a>b ? a :b;
return temp>c ?temp :c ;
}
char s[MAX],t[MAX];
short dp[MAX][MAX]; //定义的类型为short int main(){
int i,j,n;
while(scanf("%d",&n)!=EOF){
scanf("%s",s);
for(i=;i<n;i++)
t[i] = s[n-i-];
t[n] = ;
memset(dp,,sizeof(dp));
for(i=;i<=n;i++){
for(j=;j<=n;j++){
if(s[i-] == t[j-])
dp[i][j] = dp[i-][j-] + ;
dp[i][j] = max(dp[i][j],dp[i-][j],dp[i][j-]);
}
}
printf("%d\n",n-dp[n][n]);
}
return ;
}
另一种方法:dp[i][j]表示从第i个字符到第j个字符能构成的回文添加的最少字符。
 #include <stdio.h>
#define Min(a,b) (a<b?a:b)
const int MAX = ;
char ch[MAX];
short dp[MAX][MAX]={};
int main()
{
int lenth, i, j;
while(scanf("%d%s",&lenth, ch+)!=EOF)
{
for(i=lenth;i>;i--) //自底向上
{
for(j=i+;j<=lenth;j++)
{
if(ch[i]==ch[j]){
dp[i][j] = dp[i+][j-];
}
else{
dp[i][j] = Min(dp[i+][j],dp[i][j-])+;
}
}
}
printf("%d\n",dp[][lenth]);
}
return ;
}

可是在某些变态的OJ里,上面的方法仍然不能AC,这是需要引入滚动数组优化空间,比如在第一种方法之上

代码如下:

 # include<stdio.h>
# include<string.h> #define MAX 5005 int max(int a,int b,int c){
int temp;
temp = a>b ? a :b;
return temp>c ?temp :c ;
}
char s[MAX],t[MAX];
short dp[2][MAX]; int main(){
int i,j,n;
while(scanf("%d",&n)!=EOF){
scanf("%s",s);
for(i=;i<n;i++)
t[i] = s[n-i-];
t[n] = ;
memset(dp,,sizeof(dp));
for(i=;i<=n;i++){
for(j=;j<=n;j++){
if(s[i-] == t[j-])
dp[i%][j] = dp[(i-)%][j-] + ;
dp[i%][j] = max(dp[i%][j],dp[(i-)%][j],dp[i%][j-]);
}
}
printf("%d\n",n-dp[n%][n]);
}
return ;
}
上一篇:Mycat实现Mysql主从读写分离


下一篇:Spark源码剖析 - SparkContext的初始化(五)_创建任务调度器TaskScheduler