HDU 2476 String painter(区间dp)

http://acm.hdu.edu.cn/showproblem.php?pid=2476

题意:

给出两段字符串,现在要把第一串字符串转变成第二串,每次可以选择一段区间变成一个相同的字符,问至少需要操作多少次。

思路:

完全没思路的一道题目。

看了大神们的代码,先是计算出空串转换成目标串的最少操作次数,然后再去找原始串和目标串中相同的字符。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<sstream>
 6 #include<vector>
 7 #include<stack>
 8 #include<queue>
 9 #include<cmath>
10 #include<map>
11 #include<set>
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,int> pll;
15 const int INF = 0x3f3f3f3f;
16 const int maxn = 100 + 5;
17 
18 char str1[maxn],str2[maxn];
19 
20 int ans[maxn];
21 int d[maxn][maxn];
22 
23 int main()
24 {
25     //freopen("in.txt","r",stdin);
26     while(~scanf("%s%s",str1,str2))
27     {
28         memset(d,0,sizeof(d));
29 
30         int len=strlen(str1);
31 
32         for(int i=0;i<len;i++)  d[i][i]=1;  //先是单个字符转换
33 
34         for(int r=2;r<=len;r++)
35         {
36             for(int i=0;i+r-1<len;i++)
37             {
38                 int j=i+r-1;
39                 d[i][j]=d[i+1][j]+1;
40                 for(int k=i+1;k<=j;k++)
41                 {
42                     if(str2[i]==str2[k])  //如果第i个和第k个字符相同,那么对于【i,k】这个区间,可以先统一处理【i,k】
43                                           //将i和k转换成目标字符
44                         d[i][j]=min(d[i][j],d[i+1][k]+d[k+1][j]);
45                 }
46             }
47         }
48 
49         for(int i=0;i<len;i++)  ans[i]=d[0][i];  //表示前i个字符转换成目标串所需的最少操作数
50 
51         for(int i=0;i<len;i++)
52         {
53             if(str1[i]==str2[i])  //如果相等,此时前i个字符的最少操作数等于前i-1个字符的最少操作数
54             {
55                 if(i==0)  ans[i]=0;
56                 else ans[i]=ans[i-1];
57             } 
58             else                  //不相等时寻找分割点
59             {
60                 for(int k=0;k<i;k++)
61                 {
62                     ans[i]=min(ans[i],ans[k]+d[k+1][i]);
63                 }
64             }
65         }
66         printf("%d
",ans[len-1]);
67     }
68     return 0;
69 }
原文地址:https://www.cnblogs.com/zyb993963526/p/7218038.html