Uva1625 Color Length

https://vjudge.net/problem/UVA-1625
【题解】
很有思维难度的一道题
http://www.cnblogs.com/zyb993963526/p/6364069.html
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cmath>
 7 #define max(a, b) ((a) > (b) ? (a) : (b))
 8 #define min(a, b) ((a) < (b) ? (a) : (b))
 9 inline void swap(int &a, int &b)
10 {
11     int tmp = a;a = b;b = tmp;
12 }
13 inline void read(int &x)
14 {
15     x = 0;char ch = getchar(), c = ch;
16     while(ch < '0' || ch > '9')c = ch, ch = getchar();
17     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
18     if(c == '-')x = -x;
19 }
20 
21 const int INF = 0x3f3f3f3f;
22 const int MAXN = 5000 + 10;
23 
24 char s1[MAXN], s2[MAXN];
25 int t,n1,n2,dp[MAXN][MAXN], b1[30], b2[30], t1[30], t2[30];
26 
27 int cnt[MAXN][MAXN];
28 
29 
30 int main()
31 {
32     read(t);
33     for(;t;--t)
34     {
35         scanf("%s", s1 + 1);
36         n1 = strlen(s1 + 1);
37         scanf("%s", s2 + 1);
38         n2 = strlen(s2 + 1);
39         memset(b1, 0, sizeof(b1));
40         memset(b2, 0, sizeof(b2));
41         memset(t1, 0, sizeof(t1));
42         memset(t2, 0, sizeof(t2));
43         memset(cnt[0], 0, sizeof(cnt[0]));
44         for(register int i = 1;i <= n1;++ i)
45             if(!b1[s1[i] - 'A'])
46                 b1[s1[i] - 'A'] = i;
47         for(register int i = n1;i >= 1;-- i)
48             if(!t1[s1[i] - 'A'])
49                 t1[s1[i] - 'A'] = i;
50         for(register int i = 1;i <= n2;++ i)
51             if(!b2[s2[i] - 'A'])
52                 b2[s2[i] - 'A'] = i;
53         for(register int i = n2;i >= 1;-- i)
54             if(!t2[s2[i] - 'A'])
55                 t2[s2[i] - 'A'] = i;
56         for(register int i = 0;i <= n1;++ i)
57             for(register int j = 0;j <= n2;++ j)
58             {
59                 if(i)
60                 {
61                     cnt[i][j] = cnt[i - 1][j];
62                     if(b1[s1[i] - 'A'] == i && ((b2[s1[i] - 'A'] > j) || b2[s1[i] - 'A'] == 0)) 
63                         ++ cnt[i][j];
64                     if(t1[s1[i] - 'A'] == i && t2[s1[i] - 'A'] <= j)
65                         -- cnt[i][j];
66                 }
67                 else if(j)
68                 {
69                     cnt[i][j] = cnt[i][j - 1];
70                     if(b2[s2[j] - 'A'] == j && ((b1[s2[j] - 'A'] > i) || b1[s2[j] - 'A'] == 0))
71                         ++ cnt[i][j];
72                     if(t2[s2[j] - 'A'] == j && t1[s2[j] - 'A'] <= i)                    
73                         -- cnt[i][j];
74                 }
75             }
76         for(register int i = 0;i <= n1;++ i)
77             for(register int j = 0;j <= n2;++ j)
78             {
79                 if(!i && !j)continue;
80                 if(!i) dp[i][j] = dp[i][j - 1] + cnt[i][j - 1];
81                 else if(!j) dp[i][j] = dp[i - 1][j] + cnt[i - 1][j];
82                 else dp[i][j] = min(dp[i - 1][j] + cnt[i - 1][j], dp[i][j - 1] + cnt[i][j - 1]);
83             }
84         printf("%d
", dp[n1][n2]);
85     }
86     return 0;
87 }
Uva1625