UVA-10069 - Distinct Subsequences

题目链接~~>

做题感悟：这题和最长公共子序列差不多，开始没注意到数据范围，交上果断wa！！

解题思路：  DP+大数  ，用 dp [ i ] [ j ] 代表子串 j 在子串中出现的次数。

   动态方程：

                   s1[ i ] == s2[ j ]  -->    dp [ i ] [ j ] = dp [ i-1 ] [ j - 1 ] + dp [ i ] [ j -1 ] ; 即：字串 j -1 在 i 中出现的次数（应为s1[ i ] == s2[ j ] 所以相当于串 j ） + 串 j 在 串 i -1 中出现的次数。 

                   s1[ i ] ！= s2[ j ]-->    dp[ i ][ j ] = dp [ i ] [ j - 1 ] ; 即： 串 j 在 串 i -1 中出现的次数（因为s1[ i ] ！= s2[ j ]）

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int MX = 10000 + 10 ;
     
    
   

    

     

    
    

     

      int a[MX][110],b[MX][110] ;
     
    
   

    

     

    
    

     

      char s1[MX],s2[MX] ;
     
    
   

    

     

    
    

     

      void search(int j,int(*a)[110],int(*b)[110])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int c=0 ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<100 ;i++)
     
    
   

    

     

    
    

     
 if(a[j][i]+b[j][i]+c>9)
     
    
   

    

     

    
    

     

       b[j+1][i]=a[j][i]+b[j][i]+c-10 , c=1 ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       b[j+1][i]=a[j][i]+b[j][i]+c , c=0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void work(int j,int (*a)[110])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int i=0 ;i<100 ;i++)
     
    
   

    

     

    
    

     

       a[j+1][i]=a[j][i] ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void print(int x,int (*p)[110])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,j ;
     
    
   

    

     

    
    

     
 for(i=100 ;i>=0 ;i--)
     
    
   

    

     

    
    

     
 if(p[x][i])
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     
 if(i==-1)  cout<<"0" ;
     
    
   

    

     

    
    

     
 for(j=i ;j>=0 ;j--)
     
    
   

    

     

    
    

     
 cout<<p[x][j] ;
     
    
   

    

     

    
    

     
 cout<<endl ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
   int Tx ;
     
    
   

    

     

    
    

     
   scanf("%d",&Tx) ;
     
    
   

    

     

    
    

     
   while(Tx--)
     
    
   

    

     

    
    

     

         {
     
    
   

    

     

    
    

     
 scanf("%s%s",s1+1,s2+1) ;
     
    
   

    

     

    
    

     
 memset(a,0,sizeof(a)) ;
     
    
   

    

     

    
    

     
 memset(b,0,sizeof(b)) ;
     
    
   

    

     

    
    

     
 int len1=strlen(s1+1) ;
     
    
   

    

     

    
    

     
 int len2=strlen(s2+1) ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<=10000 ;i++)
     
    
   

    

     

    
    

     

       a[i][0]=1 ;
     
    
   

    

     

    
    

     
 for(int i=1 ;i<=len2 ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(int j=1 ;j<=len1 ;j++)
     
    
   

    

     

    
    

     
 if(s2[i]==s1[j])
     
    
   

    

     

    
    

     

       i%2 ? search(j-1,a,b) : search(j-1,b,a) ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       i%2 ? work(j-1,b) : work(j-1,a) ;
     
    
   

    

     

    
    

     

       i%2 ? memset(a,0,sizeof(a)) : memset(b,0,sizeof(b)) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       len2%2 ? print(len1,b) : print(len1,a) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
   return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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