首页 > 代码库 > HDU 2476 String painter 刷字符串（AC代码）区间DP
HDU 2476 String painter 刷字符串（AC代码）区间DP
题意：给出两个串s1和s2，一次只能将一个区间刷一次，问最少几次能让s1=s2
例如zzzzzfzzzzz，长度为11，我们就将下标看做0~10
先将0~10刷一次，变成aaaaaaaaaaa
1~9刷一次，abbbbbbbbba
2~8:abcccccccba
3~7:abcdddddcba
4~6:abcdeeedcab
5:abcdefedcab
这样就6次，变成了s2串了
第二个样例也一样
先将0~10刷一次，变成ccccccccccb
1~9刷一次，cdddddddddcb
2~8:cdcccccccdcb
3~7:cdcdddddcdcb
4~6:cdcdcccdcdcb
5:cdcdcdcdcdcb
最后将串尾未处理的一个字母刷一次
就变成了s2串的cdcdcdcdcdcd了
所以一共7次
思路：假设最坏情况，两串没任何一个位置是相同的，那么全都得刷，假如都这样，倒轻松了。这一步得求出任意两个位置之间的最低次数，那起码就得两个for，保存状态需要二维数组，其实只用到其上三角，对角线全是1，代表单单某个位置的字母的次数。接下来，两串可能存在某些相同的字母，可以不刷，这样就可能出现更优的解了，这一步依然得用dp啊，将范围从0开始慢慢扩大。
非递归法（参考了别人的代码）：
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #define N 110 5 using namespace std; 6 char a[N],b[N]; 7 int dp[N][N]; //dp[j][i]表示b[j~i]的最小刷法次数 8 int ans[N]; //ans[i]表示将a[0~i]刷成b[0~i]的最小刷法次数 9 int len;10 void paint_b()11 {12 int i,j,k;13 for(i=0;i<len;i++)14 for(j=i;j>=0;j--)15 {16 dp[j][i]=dp[j+1][i]+1; //j~i之间的刷法才是目标所在17 for(k=j+1;k<=i;k++)18 {19 if(b[j]==b[k])20 dp[j][i]=min(dp[j][i],dp[j+1][k]+dp[k+1][i]);21 } 22 }23 }24 void paint_a()25 {26 int i,j;27 memcpy(ans,dp,sizeof(int)*len);//先假设串a与b完全不一样，得全刷。28 if(a[0]==b[0]) ans[0]=0; else ans[0]=1; //特殊处理29 for(i=1;i<len;i++) //考虑前i个30 {31 if(a[i]==b[i])32 ans[i]=ans[i-1];33 else //第i个不同34 {35 for(j=0;j<i;j++ ) //从前往后扫36 if(a[j]==b[j]) //b[0~i]之间可能存在有些与a的相同，不必刷。37 ans[i]= min(ans[i],ans[j-1]+dp[j+1][i]);38 }39 }40 }41 int main()42 {43 while(cin>>a>>b)44 {45 len=strlen(a);46 paint_b(); //求串b中每两字母之间的最小刷法次数，并更新在dp的上三角中。47 paint_a(); //将串a刷成串b的最小刷法次数，并更新在ans中。48 printf("%d\n",ans[len-1]);49 memset(dp,0,sizeof(dp));50 }51 return 0;52 }
递归法（还没想出来）：
HDU 2476 String painter 刷字符串（AC代码）区间DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。