Uva 4394 String painter

看见某dalao在做这道题，感觉很有趣。

题意：

给你两个字符串s、t，每次操作把s的某个区间变成同一个字符。问最少操作怎么把它变成t。

题解：

我们先定义一个$cnt[i]$表示前i位需要多少次操作。

显然当$s[i]==t[i]$时，$cnt[i]=cnt[i-1]$。

不相等时，我们可以枚举端点$j< i$满足$t[j]==t[i] \& s[j]!=t[j]$则

$$cnt[i]=min(cnt[i],dp(j+1,i-1,t[i])+1+(j>0?cnt[j-1]:0))$$

dp过程是找出$l-r$先涂上某字符串再恢复的最小花费。

这个转移也是枚举端点瞎搞下就好了。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 110
#define inf 0x3f3f3f3f
using namespace std;
char s[N],t[N];
int cnt[N],f[N][N][30];
int dp(int st,int ed,char now)
{
    if(f[st][ed][now-'a']!=-1)
        return f[st][ed][now-'a'];
    if(st>ed)
        return 0;
    if(st==ed)
        return now==t[st]?0:1;
    if(now==t[ed])
        return dp(st,ed-1,now);
    int ans=inf;
    for(int i=ed;i>=st;i--)
        if(t[i]==t[ed])
            ans=min(ans,dp(st,i-1,now)+dp(i,ed,t[ed])+1);
    return f[st][ed][now-'a']=ans;
}
main()
{
    while(~scanf("%s%s",s,t))
    {
        memset(f,-1,sizeof f);
        int len=strlen(s);
        if (s[0]==t[0])
            cnt[0]=0;
        else
            cnt[0]=1;
        for (int i=1;i<len;i++)
            if (s[i]==t[i])
                cnt[i]=cnt[i-1];
            else
            {
                cnt[i]=inf;
                for (int j=i;j>=0;j--)
                    if (t[j]==t[i] && s[j]!=t[j])
                        cnt[i]=min(cnt[i],dp(j+1,i-1,t[i])+1+(j>0?cnt[j-1]:0));
            }
        printf("%d\n",cnt[len-1]);
    }
}