首页 > 题解 > Uva 4394 String painter

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$先涂上某字符串再恢复的最小花费。

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

代码:


2 COMMENTS

  1. Malt2017-09-11 上午11:06

    一直不会做这道题,看了好多题解还是不太懂。
    但我怎么发现你跟这个写的一样呢?http://blog.csdn.net/u014664226/article/details/46492539

    • 远航之曲2017-09-11 下午4:05

      应该是巧合吧。。数组名都一样也很鬼啊。我觉得题解思路很直接,你哪里不懂啊。。

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×