首页 > 代码库 > HDU 2476 String painter（字符串转变）

HDU 2476 String painter（字符串转变）

2024-07-08 23:47:08   215人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2476

题意：给定两个长度相同的串A和B。每次操作可以将A的连续一段改变为另一个字母。求将A转换成B最少需要多少次操作？

思路：首先，我们假设没有A串，那么这就跟 BZOJ1260是一样的了,即答案为DFS(0,n-1)。。。但是这里有了A串就有可能使得操作次数更少。因为可能有些对应位置字母是相同的。我们设 ans[i]表示前i个字母变成一样的，那么若A[i]=B[i]则ans[i]=ans[i-1]+1。否则 ans[i]=min(ans[j]+DFS(j+1,i))，想想为啥能这样呢？因为前i个的最优答案必然是从某个位置j之后，A和B完全不同，这就是 DFS(j+1,i)了。。。

 

char s[N],p[N];int f[N][N],n,ans[N];int DFS(int L,int R){    if(L>R) return 0;    if(L==R) return 1;    if(f[L][R]!=-1) return f[L][R];    f[L][R]=INF;    int i;    for(i=L;i<R;i++) f[L][R]=min(f[L][R],DFS(L,i)+DFS(i+1,R));    if(p[L]==p[R]) f[L][R]--;    return f[L][R];}int main(){    while(scanf("%s%s",s,p)!=-1)    {        n=strlen(s); clr(f,-1);        int i,j;        ans[0]=s[0]!=p[0];        for(i=1;i<n;i++)        {            ans[i]=DFS(0,i);            if(s[i]==p[i]) ans[i]=min(ans[i],ans[i-1]);            else             {                for(j=0;j<=i;j++) ans[i]=min(ans[i],ans[j]+DFS(j+1,i));            }        }        PR(ans[n-1]);    }}

 

 

 


联系
我们