HDU 4681 String(2013多校8 1006題DP)

String
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 11    Accepted Submission(s): 4
Problem Description
Given 3 strings A, B, C, find the longest string D which satisfy the following rules:
a) D is the subsequence of A
b) D is the subsequence of B
c) C is the substring of D
Substring here means a consecutive subsequnce.
You need to output the length of D.
 
 
Input
The first line of the input contains an integer T(T = 20) which means the number of test cases.
For each test case, the first line only contains string A, the second line only contains string B, and the third only contains string C.
The length of each string will not exceed 1000, and string C should always be the subsequence of string A and string B.
All the letters in each string are in lowercase.
 
 
Output
For each test case, output Case #a: b. Here a means the number of case, and b means the length of D.
 
 
Sample Input
2 aaaaa aaaa aa abcdef acebdf cf
 
 
Sample Output
Case #1: 4 Case #2: 3
Hint
For test one, D is "aaaa", and for test two, D is "acf".
 
 
Source
2013 Multi-University Training Contest 8
 
 
Recommend
zhuyuanchen520
 
 
 
明らかなDP問題.
最も長い公共のサブストリングを求めて、正和はそれぞれ1回求めて、dpとdp 3を得ます
dp[i][j]はstr 1の前i文字とstr 2の前j文字が最も長い共通サブ列を表す.
dp 3[i][j]はstr 1の後i文字とstr 2の後j文字が最も長い共通サブ列を表す.
 
dp 1[i][j]はstr 3の前j文字を表し、str 1の前i文字と一致し、最後の一致開始位置は-1で一致しないことを表す.
dp 2同様
 
次にstr 3がstr 1,str 2で一致する終点を列挙する
 
 

 1 /* ***********************************************
 2 Author        :kuangbin
 3 Created Time  :2013/8/15 12:34:55
 4 File Name     :F:\2013ACM  \2013  8\1006.cpp
 5 ************************************************ */
 6 
 7 #include <stdio.h>
 8 #include <string.h>
 9 #include <iostream>
10 #include <algorithm>
11 #include <vector>
12 #include <queue>
13 #include <set>
14 #include <map>
15 #include <string>
16 #include <math.h>
17 #include <stdlib.h>
18 #include <time.h>
19 using namespace std;
20 
21 const int MAXN = 1010;
22 char str1[MAXN],str2[MAXN],str3[MAXN];
23 int dp1[MAXN][MAXN];
24 int dp2[MAXN][MAXN];
25 int dp[MAXN][MAXN];
26 int dp3[MAXN][MAXN];
27 int main()
28 {
29     //freopen("in.txt","r",stdin);
30     //freopen("out.txt","w",stdout);
31     int T;
32     scanf("%d",&T);
33     int iCase = 0;
34     while(T--)
35     {
36         iCase++;
37         scanf("%s%s%s",str1,str2,str3);
38         int len1 = strlen(str1);
39         int len2 = strlen(str2);
40         int len3 = strlen(str3);
41         for(int i = 0; i <= len1;i++)
42             dp[i][0] = 0;
43         for(int i = 0;i <= len2;i++)
44             dp[0][i] = 0;
45         for(int i = 1;i <= len1;i++)
46             for(int j = 1;j <= len2;j++)
47             {
48                 dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
49                 if(str1[i-1] == str2[j-1])
50                     dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1);
51             }
52         for(int i = 0; i <= len1;i++)
53             dp3[i][0] = 0;
54         for(int i = 0;i <= len2;i++)
55             dp3[0][i] = 0;
56         for(int i = 1;i <= len1;i++)
57             for(int j = 1;j <= len2;j++)
58             {
59                 dp3[i][j] = max(dp3[i-1][j],dp3[i][j-1]);
60                 if(str1[len1-i] == str2[len2-j])
61                     dp3[i][j] = max(dp3[i][j],dp3[i-1][j-1]+1);
62             }
63         for(int i = 1;i <= len3;i++)
64             dp1[0][i] = -1;
65         for(int i = 0;i <= len1;i++)
66             dp1[i][0] = i;
67         for(int i = 1;i <= len1;i++)
68             for(int j = 1;j <= len3;j++)
69             {
70                 if(str1[i-1] == str3[j-1])
71                     dp1[i][j] = dp1[i-1][j-1];
72                 else dp1[i][j] = dp1[i-1][j];
73             }
74         for(int i = 1;i <= len3;i++)
75             dp2[0][i] = -1;
76         for(int i = 0;i <= len2;i++)
77             dp2[i][0] = i;
78         for(int i = 1;i <= len2;i++)
79             for(int j = 1;j <= len3;j++)
80             {
81                 if(str2[i-1] == str3[j-1])
82                     dp2[i][j] = dp2[i-1][j-1];
83                 else dp2[i][j] = dp2[i-1][j];
84             }
85         int ans = 0;
86         for(int i = 0;i <= len1;i++)
87             for(int j = 0;j <= len2;j++)
88             {
89                 int t1 = dp1[len1-i][len3];
90                 int t2 = dp2[len2-j][len3];
91                 if(t1 == -1 || t2 == -1)continue;
92                 ans = max(ans,dp3[i][j]+dp[t1][t2]);
93             }
94         printf("Case #%d: %d
",iCase,ans+len3);
95     }
96     return 0;
97 }