会python真的可以为所欲为0(回)
359天前
这里还有人吗1(回)
544天前这里还有人吗0(回)
544天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
768天前到处都是羊，不想上班0(回)
848天前
鸽子
0(回)
852天前/* |
将字符串逆序，找出原字符串与该字符串的公共子序列，则其余部分为需要添加的字符 |
状态转移方程参考最长公共子字符串 |
http://www.cnblogs.com/qq188380780/p/6678471.html |
*/ |
#include<cstdio> |
#include<cstring> |
#define Max(a,b) ((a)>(b)?(a):(b)) |
char a[1005],b[1005]; |
int d[1005][1005]; |
void solven(int len) |
{ |
int i,j; |
for(i=1; i<=len; ++i) |
{ |
for(j=1; j<=len; ++j) |
{ |
if(a[i-1] == b[j-1]) |
d[i][j] = d[i-1][j-1] + 1; |
else |
d[i][j] = Max(d[i-1][j],d[i][j-1]); |
} |
} |
} |
int main() |
{ |
int t,i,j,len; |
scanf("%d",&t); |
while(t--) |
{ |
memset(d,0,sizeof d); |
scanf("%s",a); |
len = strlen(a); |
for(i=0; i<len; ++i) |
b[i] = a[len-1-i]; |
solven(len); |
printf("%d\n",len-d[len][len]); |
} |
return 0; |
} |
//空间优化，与最长公共子序列一样 |
#include<cstdio> |
#include<cstring> |
char a[1005],b[1005]; |
int d[1005]; |
void solven(int len) |
{ |
int i,j,t,temp; |
for(i=0; i<len; ++i) |
{ |
for(j=t=0; j<len; ++j) |
{ |
temp = d[j]; |
if(a[i] == b[j]) |
d[j] = t + 1; |
else if(d[j] < d[j-1]) |
d[j] = d[j-1]; |
t = temp; |
} |
} |
} |
int main() |
{ |
int t,i,j,len; |
scanf("%d",&t); |
while(t--) |
{ |
memset(d,0,sizeof d); |
scanf("%s",a); |
len = strlen(a); |
for(i=0; i<len; ++i) |
b[i] = a[len-1-i]; |
solven(len); |
printf("%d\n",len-d[len-1]); |
} |
return 0; |
} |
//另可不必再开数组存逆序，只需要记录位置即可 |
#include<cstdio> |
#include<cstring> |
char a[1005]; |
int d[1005]; |
void solven(int len) |
{ |
int i,j,t,temp; |
for(i=0; i<len; ++i) |
{ |
for(j=t=0; j<len; ++j) |
{ |
temp = d[j]; |
if(a[i] == a[len-1-j]) |
d[j] = t + 1; |
else if(d[j] < d[j-1]) |
d[j] = d[j-1]; |
t = temp; |
} |
} |
} |
int main() |
{ |
int t,i,j,len; |
scanf("%d",&t); |
while(t--) |
{ |
memset(d,0,sizeof d); |
scanf("%s",a); |
len = strlen(a); |
for(i=0; i<len; ++i) |
b[i] = a[len-1-i]; |
solven(len); |
printf("%d\n",len-d[len-1]); |
} |
return 0; |
} |
