HDU 2476：String painter （区间DP）

HDU 2476：String painter （区间DP）

Problem Description

There are two strings A and B with equal length. Both strings are made up of lower case letters.Now you have a powerful string painter. With the help of the painter, you can change a segment ofcharacters of a string to any other character you want. That is, after using the painter, thesegment is made up of only one kind of character. Now your task is to change A to B using stringpainter. What’s the minimum number of operations?

Input

Input contains multiple cases. Each case consists of two lines:The first line contains string A.The second line contains string B.The length of both strings will not be greater than 100.

Output

A single line contains one integer representing the answer.

Sample Input

zzzzzfzzzzzabcdefedcbaababababababcdcdcdcdcdcd

Sample Output

67

题意

给出两个字符串，每次我们可以把一个字符串的一个区间刷成同一个字母，问最少多少步可以把第一个字符串变为第二个字符串

思路

假设有一个字符串abcddcba，我们先考虑区间[0,7]也就是abcddcba，假如我们认为每次刷一位，不考虑优化的情况下的答案是8，也就是刷8次可以得到这个区间，但是，可以发现的是区间两个端点的值相等，所以我们可以在第一次用a来刷这个区间，假如用dp[0][7]来表示建立这个区间的最小次数,在端点相等的情况下我们可以假设去掉左端点，因为二者是等价的，然后区间变为bcddcba，如此便是一次优化，然后我们可以分解区间，然后分别优化求解两个区间

这样便可以得到单个字符串建立的最小次数，由串1变为串2，如果相同位置字符相同的话我们可以不刷这个位置。

AC代码

#include #includeusing namespace std;#include#includechar s1[105],s2[105];int dp[105][105],ans[105];//dp[i][j]表示从i到j的最小次数int main(){ while(gets(s1)) { gets(s2); int len=strlen(s1); memset(dp,0,sizeof(dp)); for(int j=0; j=0; i--) { dp[i][j]=dp[i+1][j]+1; //先假设无优化刷当前区间 for(int k=i+1; k<=j; k++) //用k来分割区间 if(s2[i]==s2[k]) //找到相等位置，更新最小次数 dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]); } for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。