本文共 2943 字，大约阅读时间需要 9 分钟。
1、
2、数据好大，longlong也不对，用大数相加
dp[i][j]表示b的前i个字符在a的前j个字符中出现的次数
状态转移方程;
if(b[i-1]==a[j-1])//如果b的第i个字符和a的第j个字符相同，那么dp[i][j]=dp[i][j-1]+dp[i-1][j-1]
else
dp[i][j]=dp[i][j-1];
题目大意;
给定两个序列a,b,求出a中有多少个b序列，只要顺序相同即可， 不必要连续
题目；
Problem E
Distinct Subsequences
Input: standard input
Output: standard output
A subsequence of a given sequence is just the given sequence with some elements (possibly none) left out. Formally, given a sequence X =x1x2…xm, another sequence Z = z1z2…zk is a subsequence of X if there exists a strictly increasing sequence <i1, i2, …, ik> of indices of Xsuch that for all j = 1, 2, …, k, we have xij = zj. For example, Z = bcdb is a subsequence of X = abcbdab with corresponding index sequence< 2, 3, 5, 7 >.
In this problem your job is to write a program that counts the number of occurrences of Z in X as a subsequence such that each has a distinct index sequence.
Input
The first line of the input contains an integer N indicating the number of test cases to follow.
The first line of each test case contains a string X, composed entirely of lowercase alphabetic characters and having length no greater than 10,000. The second line contains another string Z having length no greater than 100 and also composed of only lowercase alphabetic characters. Be assured that neither Z nor any prefix or suffix of Z will have more than 10100 distinct occurrences in X as a subsequence.
Output
For each test case in the input output the number of distinct occurrences of Z in X as a subsequence. Output for each input set must be on a separate line.
Sample Input
2 babgbag bag rabbbit rabbit
Sample Output
5 34、AC代码：
#include超时代码：（思路对，加上大数相加即可）#include #include using namespace std;char a[10005];char b[105];char dp[105][10005][105];void add(char *c,char *a,char *b){ int la=strlen(a); int lb=strlen(b); int lc=max(la,lb); memset(c,0,(lc+2)*sizeof(c[0])); for(int i=la-1,j=lc;i>=0;i--,j--) c[j]+=a[i]-'0'; for(int i=lb-1,j=lc;i>=0;i--,j--) c[j]+=b[i]-'0'; for(int i=lc;i>0;c[i]+='0',i--) { if(c[i]>9) { c[i]-=10; c[i-1]++; } } if(!c[0]) { for(int i=0;i
#include#include #define N 10005char a[N];char b[105];int dp[105][N];//dp[i][j]表示子串的前i个字符在母串的前j个字符中出现的次数int main(){ int t; scanf("%d",&t); while(t--) { scanf("%s%s",a,b); int la=strlen(a); int lb=strlen(b); memset(dp,0,sizeof(dp)); for(int i=0;i<=la;i++) dp[0][i]=1; for(int i=1;i<=lb;i++) { for(int j=i;j<=la;j++) { if(a[j-1]==b[i-1]) dp[i][j]=dp[i-1][j-1]+dp[i][j-1]; else dp[i][j]=dp[i][j-1]; } } printf("%d\n",dp[lb][la]); } return 0;}
转载地址：http://khddi.baihongyu.com/