本文主要是介绍UVA 10069 Distinct Subsequences(dp + 高精度)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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
2babgbag
bag
rabbbit
rabbit
Sample Output
53
题意：给定两个字符串，求b作为a的字串有几种情况。
思路：dp，类似LCS问题，i作为b的第i个字符，j作为a的第j个字符。 如果a[j] != b[i]。那么dp[i][j] = dp[i][j - 1]。如果相等。则多加上dp[i - 1][j - 1]。即dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]。注意要用高精度加法
代码：
#include <stdio.h>
#include <string.h>
const int N = 10005, M = 105;int t, i, j, n, m;
int A[M], B[M], C[M];
char a[N], b[M], c[M], dp[M][N][M];
void add(char *a, char *b) {memset(c, 0, sizeof(c));memset(A, 0, sizeof(A));memset(B, 0, sizeof(B));memset(C, 0, sizeof(C));int i, lena = strlen(a), lenb = strlen(b), len;for (i = 0; i < lena; i ++)A[lena - 1 - i] = a[i] - '0';for (i = 0; i < lenb; i ++)B[lenb - 1 - i] = b[i] - '0';len = lena > lenb ? lena : lenb;for (i = 0; i < len; i ++) {C[i] += A[i] + B[i];C[i + 1] += C[i] / 10;C[i] %= 10;}while (C[len] == 0 && len > 0)len --;for (i = len; i >= 0; i --) {c[len - i] = C[i] + '0';}
}
int main() {scanf("%d", &t);while (t --) {memset(dp, 0, sizeof(dp));scanf("%s%s", a, b); n = strlen(a); m = strlen(b);for (i = 0; i <= n; i ++)strcpy(dp[0][i], "1");for (i = 1; i <= m; i ++) {for (j = 1; j <= n; j++) {strcpy(dp[i][j], dp[i][j - 1]);if (b[i - 1] == a[j - 1]) {add(dp[i][j], dp[i - 1][j - 1]);strcpy(dp[i][j], c);}}}printf("%s\n", dp[m][n]);}return 0;
}这篇关于UVA 10069 Distinct Subsequences(dp + 高精度)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
