[UVA][dp] 11081 - Strings
Problem H
Strings
Input: Standard Input
Output: Standard Output
Given 3 strings of only lowercase letter you have to count the number of ways you can construct the third 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 following strings “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
題目描述：
不改變 A, B兩個字串的順序，抽出來組合成 C，問方法數若干？
題目解法：
狀態一定是 dp[lc][la][lb], 表示成當前 substringC, substringA, substringB
然後嘗試將 substringC 的 tail 去匹配 substringA, substringB 的其中一個字串，
接著去掉匹配的字串之後，繼續求解。
整體來說最慘到 O(n^4)，但如果字符種類差異很大速度會比較快，有機會達到 O(n^3)，甚至更小。
#include <string.h>
int dp[65][65][65];
char used[65][65][65];
char a[65], b[65], c[65];
int la, lb, lc;
int dfs(int i, int j, int k) {
if(i == 0)
return 1;
int &val = dp[i][j][k];
if(used[i][j][k]) return val;
used[i][j][k] = 1;
val = 0;
int p;
for(p = j-1; p >= 1; p--) {
if(a[p] == c[i]) {
val += dfs(i-1, p, k);
}
}
for(p = k-1; p >= 1; p--) {
if(b[p] == c[i]) {
val += dfs(i-1, j, p);
}
}
if(val >= 10007)
val %= 10007;
return val;
}
int main() {
int testcase;
scanf("%d", &testcase);
while(testcase--) {
scanf("%s %s %s", a+1, b+1, c+1);
memset(used, 0, sizeof(used));
dp[0][0][0] = 1;
la = strlen(a+1), lb = strlen(b+1), lc = strlen(c+1);
int ret = dfs(lc, la+1, lb+1);
printf("%d\n", ret);
}
return 0;
}
/*
2
abbcd bccde abcde
abbcd bccde ab
*/