uva 10069 Distinct Subsequences 【dp+大数】

阳光穿透心脏的1/2处 2022-08-12 03:00 133阅读 0赞

题目：[uva 10069 Distinct Subsequences][]

题意：给出一个子串 x 和母串 s ，求子串在母串中的不同序列的个数？

分析：定义dp【i】【j】：x 的前 i 个字母在 s 的前 j 个字母中的出现次数；

**dp \[ i \] \[ j \] = dp \[ i \] \[ j - 1 \] ;  
if ( x\[ i \] == s \[ j \] )  
dp\[i\]\[j\]=add(dp\[i-1\]\[j-1\],dp\[i\]\[j\]);**

**注意点：1：出现次数非常大，要用大数加法**

**2:：注意初始化**

**AC代码：**

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include <map>
    #include <cmath>
    #include <vector>
    #include <algorithm>
    using namespace std;
    const int N = 10050;
    string dp[105][N];
    string sum(string s1,string s2)
    {
    	if(s1.length()<s2.length())
    	{
    		string temp=s1;
    		s1=s2;
    		s2=temp;
    	}
    	int i,j;
    	for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--)
    	{
    		s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0));   //注意细节
    		if(s1[i]-'0'>=10)
    		{
    			s1[i]=char((s1[i]-'0')%10+'0');
    			if(i) s1[i-1]++;
    			else s1='1'+s1;
    		}
    	}
    	return s1;
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int T;
        scanf("%d",&T);
        while(T--)
        {
            string s,x;
            cin>>s>>x;
            string ss="1",xx="2";
            ss+=s,xx+=x;
            for(int i=0;i<xx.size();i++)
                dp[i][0]="0";
            for(int i=0;i<ss.size();i++)
                dp[0][i]="1";
            for(int i=1;i<xx.size();i++)
            {
                for(int j=1;j<ss.size();j++)
                {
                    dp[i][j]=dp[i][j-1];
                    if(xx[i]==ss[j])
                        dp[i][j]=sum(dp[i-1][j-1],dp[i][j]);
                    //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
                }
    
            }
            cout<<dp[xx.size()-1][ss.size()-1]<<endl;
        }
        return 0;
    }

[uva 10069 Distinct Subsequences]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1010