做题感悟：开始做这题时每次向前寻找最优时就用LCS判断一下是否可以转化，结果超时，最后看了一下才知道原来这样。
解题思路：
判断当前字符串时，枚举每一种情况，包括添加，删除，改写一个字符，然后就是关键之处了，寻找的时候用二分查找，有的人可能不解，这样怎么用二分呢 ？ 你太低估二分的实力了，因为给的字符串是有序的可以用字符串比较函数比较，这样就可以二分了。
代码：
#include<iostream>
#include<iomanip>
#include<string.h>
#include<string>
#include<stdio.h>
#include<stdlib.h>
using namespace std ;
const int MY = 20 ;
const int MX = 25000 + 10 ;
int n ;
int dp[MX] ;
char s[MX][MY],str[MY] ;
void change(char *s1,char *s2,int x,char ch)// 改变对应位置字符
{
int p=0 ;
for(int i=0 ;s1[i] ;i++)
if(i==x)
s2[p++]=ch ;
else s2[p++]=s1[i] ;
s2[p++]='\0' ;
}
void add(char *s1,char *s2,int x,char ch) // 添加字符
{
int len=strlen(s1),p=0 ;
for(int i=0 ;i<x ;i++)
s2[p++]=s1[i] ;
s2[p++]=ch ;
for(int i=x ;i<len ;i++)
s2[p++]=s1[i] ;
s2[p++]='\0' ;
}
void del(char *s1,char *s2,int x) // 删除对应字符
{
int p=0 ;
for(int i=0 ;s1[i] ;i++)
if(i!=x)
s2[p++]=s1[i] ;
s2[p++]='\0' ;
}
void tran(char *s1,char *s2,int i,int flag,char ch)
{
if(!flag) change(s1,s2,i,ch) ;
else if(flag==1) add(s1,s2,i,ch) ;
else del(s1,s2,i) ;
}
int binary_search(int le,int rt,char *str) // 二分
{
int mid ;
while(le<rt)
{
mid=(le+rt)/2 ;
if(!strcmp(s[mid],str)) return mid ;
else strcmp(s[mid],str)>0 ? rt=mid : le=mid+1 ;
}
return -1 ;
}
void work()
{
int ans=0 ;
memset(dp,0,sizeof(dp)) ;
for(int i=0 ;i<n ;i++)
{
dp[i]=1 ;
int len=strlen(s[i]) ;
for(int t=0 ;t<3 ;t++) // 枚举每一种情况
{
for(int j=0 ;j<=len ;j++)
{
if(j==len&&t!=1) continue ;
for(int k=0 ;k<26 ;k++)
{
tran(s[i],str,j,t,k+'a') ;
if(strcmp(s[i],str)<0) break ;
int mx=binary_search(0,i,str) ;
if(mx!=-1)
dp[i]=max(dp[i],dp[mx]+1) ;
}
}
}
ans = max(ans,dp[i]) ;
}
cout<<ans<<endl ;
}
int main()
{
n=0 ;
while(cin>>s[n++]) ;
n-- ;
work() ;
return 0 ;
}