UVa 11081 Strings(DP 문자열 일치)

제목:
세 번째 문자열을 구성하는 세 번째 문자열의 개수를 구하는 세 개의 문자열을 지정합니다.
아이디어:
제목의 사고방식은 마치 일찍이 만난 적이 있는 것 같은데, 단지 원열과 목표열의 일치일 뿐이다.
수학 귀납법을 이용한 사상은 바로 i번째 문자열이 참여하거나 일치하지 않는 것이다.이 사고방식을 따라 문제가 순조롭게 풀리다.
처음에 나는 dp수 그룹만 사용했지만 어쩔 수 없이 모두 WA였다. 인터넷에 더 간단한 코드가 있는 것을 보았지만 사실 사고방식은 모두 일치했다.

#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <algorithm>

using namespace std; const int MAXN = 70; int d1[MAXN][MAXN][MAXN], d2[MAXN][MAXN][MAXN], d[MAXN][MAXN][MAXN]; char b1[MAXN], b2[MAXN], b3[MAXN]; int solve() { int len1 = strlen(b1 + 1); int len2 = strlen(b2 + 1); int len3 = strlen(b3 + 1); memset(d, 0, sizeof(d)); memset(d1, 0, sizeof(d1)); memset(d2, 0, sizeof(d2)); for (int i = 0; i <= len1; ++i) for (int j = 0; j <= len2; ++j) d[i][j][0] = d1[i][j][0] = d2[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) { d1[i][j][k] = d1[i-1][j][k]; if (b1[i] == b3[k]) d1[i][j][k] += d[i-1][j][k-1]; d1[i][j][k] %= 10007; } if (j) { d2[i][j][k] = d2[i][j-1][k]; if (b2[j] == b3[k]) d2[i][j][k] += d[i][j-1][k-1]; d2[i][j][k] %= 10007; } d[i][j][k] = (d1[i][j][k] + d2[i][j][k]) % 10007; } return d[len1][len2][len3]; } int main() { int cases; scanf("%d", &cases); while (cases--) { scanf("%s %s %s", b1+1, b2+1, b3+1); printf("%d
", solve()); } return 0; }