dp+高精度 uva-10069-Distinct Subsequences


 
 
 
题目大意：
 
给两个字符串A，B，求B串在A串中出现的个数。
 
 
 
解题思路：
 
dp+高精度。
 
dp[i][j][k]表示串B的前i个在串A的前j个中出现的个数,k表示位数，每一位表示4位十进制的数。
 
如果save2[i]==save1[j]  则dp[i][j]=dp[i][j-1]+dp[i-1][j-1]; 注意处理初始化的问题。
 
如果save2[i]!=save1[j]   则dp[i][j]=dp[i][j-1];
 
高精度：每一位表示4位十进制的数，如果一位一位的相加的话会超时。
 
 
 
代码：
 
[cpp]  
#include<iostream>  
#include<cmath>  
#include<cstdio>  
#include<cstdlib>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<stack>  
#include<queue>  
#define eps 1e-6  
#define INF (1<<20)  
#define PI acos(-1.0)  
using namespace std;  
  
char save1[11000],save2[120];  
int dp[120][11000][30];   //dp[i][j]表示Zi在Aj中一共有多少个  一位表示4位10000  
  
  
void add(int i,int j)  
{  
    int i1=i,j1=j-1,i2=i-1,j2=j-1;  
  
    for(int k=1;k<=30;k++)  
    {  
        dp[i][j][k+1]+=(dp[i1][j1][k]+dp[i2][j2][k])/10000; //进位  
        dp[i][j][k]+=(dp[i1][j1][k]+dp[i2][j2][k])%10000;  
    }  
    return ;  
}  
  
int main()  
{  
    int ca;  
  
    scanf("%d",&ca);  
    while(ca--)  
    {  
        scanf("%s%s",save1,save2);  
  
        int len1=strlen(save1),len2=strlen(save2);  
  
        memset(dp,0,sizeof(dp));  
  
        for(int j=0;j<=len1;j++) //注意初始化，用于构建第一种情况  
            dp[0][j][1]=1;  
  
        for(int i=1;i<=len2;i++)  
            for(int j=1;j<=len1;j++)  
            {  
                if(save2[i-1]==save1[j-1])  
                {  
                    //dp[i][j]=dp[i][j-1]+dp[i-1][j-1]; //可以从dp[i][j-1]继承过来，也可以新增dp[i-1][j-1]个  
                    add(i,j);  
                }  
                else  
                {  
                    //dp[i][j]=dp[i][j-1];  
                    for(int k=1;k<=30;k++)  //直接复制  
                        dp[i][j][k]=dp[i][j-1][k];  
  
                }  
            }  
        //printf("%lld\n",dp[len2][len1]);  
        int i;  
        for(i=30;dp[len2][len1][i]==0&&i>=1;i--)  //除掉前置零  
            ;  
        printf("%d",dp[len2][len1][i]); //把第一个处理，不用4位处理。  
        i--;  
        for(;i>=1;i--)  
            printf("%04d",dp[len2][len1][i]); //注意前置零  
        putchar('\n');  
    }  
    return 0;  
}

补充：软件开发 , C++ ,