HDU 2476 区间DP String painter

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 100 + 10;
 8 
 9 int n;
10 char s1[maxn], s2[maxn];
11 
12 int d[maxn][maxn], a[maxn];
13 
14 int main()
15 {
16     while(scanf("%s%s", s1 + 1, s2 + 1) == 2)
17     {
18         n = strlen(s1 + 1);
19         for(int i = 1; i <= n; i++) d[i][i] = 1;
20 
21         for(int l = 2; l <= n; l++)
22             for(int i = 1; i + l - 1 <= n; i++)
23             {
24                 int j = i + l - 1;
25                 d[i][j] = d[i + 1][j] + 1;
26                 for(int k = i + 1; k <= j; k++) if(s2[i] == s2[k])
27                     d[i][j] = min(d[i][j], d[i+1][k-1] + d[k][j]);
28             }
29 
30         if(s1[1] == s2[1]) a[1] = 0; else a[1] = 1;
31         for(int i = 2; i <= n; i++)
32         {
33             a[i] = d[1][i];
34             if(s1[i] == s2[i]) a[i] = a[i - 1];
35             else
36             {
37                 for(int j = 1; j < i; j++) a[i] = min(a[i], a[j] + d[j+1][i]);
38             }
39         }
40 
41         printf("%d
", a[n]);
42     }
43 
44     return 0;
45 }