首页 > 代码库 > uva 10069 Distinct Subsequences 【dp+大数】
uva 10069 Distinct Subsequences 【dp+大数】
题目: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 【dp+大数】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。