UVA 10029 - Edit Step Ladders

题目链接~~>

做题感悟：开始做这题时每次向前寻找最优时就用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 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/38146259