UVALive 4394 String painter ——（区间DP）

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