本文主要是介绍UVA 11081 Strings(dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
string by combining two subsequences from the first two strings.
After deleting 0 or more characters from a string we can get its subsequence. For example “a”, “b”, “c”, “ab”, “ac”, “bc” and “abc” all the strings are the subsequences of “abc”. A subsequence may also be empty.
Now suppose there are two subsequences “abc” and “de”. By combining them you can get the followingstrings “abcde”, “abdce”, “abdec”, “adbce”, “adbec”, “adebc”, “dabce”, “dabec”, “daebc” and “deabc”.
Input
The first line of the input contains a single integer T (0<T<271) indicating the number of test cases. Each test case contains 3 strings containing only lowercase characters. The lengths of the strings are between 1 and 60.
Output
For each test case output a single integer denoting the number of ways you can construct the third string from the first two string by the above way. The result may be very large. You should output the result%10007.
Sample Input Output for Sample Input
| 2 abc abc abc abbcd bccde abcde | 8 18
|
Problemsetter: Abdullah-al-Mahmud
Special Thanks: Md. Kamruzzaman
题意：给定3个字符串， 要求出能用a和b子串（包括空串）组合成c串的总数。
思路： dp。。没思路。看题解。。大概看懂了。f[i][j][k]，i，j，k分别表示三个字符串当前的位置。要开两个数组来表示，否则无法表示出空串情况。 有点累死LCS问题。。但是这个确实不好想
代码：
#include <stdio.h>
#include <string.h>
const int MAXN = 65;
int n;
char s1[MAXN], s2[MAXN], s3[MAXN];
int f1[MAXN][MAXN][MAXN], f2[MAXN][MAXN][MAXN], f[MAXN][MAXN][MAXN];
int main() {scanf("%d", &n);while (n --) {scanf("%s%s%s", s1 + 1, s2 + 1, s3 + 1);int len1 = strlen(s1 + 1);int len2 = strlen(s2 + 1);int len3 = strlen(s3 + 1);memset(f1, 0, sizeof(f1));memset(f2, 0, sizeof(f2));memset(f, 0, sizeof(f));for (int i = 0; i <= len1; i ++)for (int j = 0; j <= len2; j ++)f[i][j][0] = f1[i][j][0] = f2[i][j][0] = 1;for (int k = 1; k <= len3; k ++)for (int i = 0; i <= len1; i ++)for (int j = 0; j <= len2; j ++) {if (i) {f1[i][j][k] = f1[i - 1][j][k];if (s1[i] == s3[k])f1[i][j][k] += f[i -1][j][k - 1];f1[i][j][k] %= 10007;}if (j) {f2[i][j][k] = f2[i][j - 1][k];if (s2[j] == s3[k])f2[i][j][k] += f[i][j - 1][k - 1];f2[i][j][k] %= 10007;}f[i][j][k] = (f1[i][j][k] + f2[i][j][k]) % 10007;}printf("%d\n", f[len1][len2][len3]);}return 0;
}这篇关于UVA 11081 Strings(dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
