HDU 2746 ——String painter

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

   這道題，大多數部落格都是一種解法:就是先得到無顔色的字元串塗色為所需字元串的最小次數（1），然後基于此去找當原先的字元串并不是無顔色的而是有固定顔色時的最小值（2）。怎樣找呢？因為字元串原先已有顔色，是以（1）中有許多塗色是不必要的，它的最小值并不是真正的最小值，故隻需在（1）的基礎上“做減法”，找到真正的最小值就好了。

   但是，其實這樣子做是不對的，因為（1）的情況下塗色的最小次數是不一定大于（2）的，即如果隻是想着在（1）的基礎上做減法是可能帶來的錯誤的，可能要通過加法來修正(1)的最小次數！

   比如：當第一個字元串為ab，第二個字元串為cc時，就會出現錯誤：正确答案為2，但是上面的做法得到的答案卻是1，因為無顔色的字元串塗色成cc當然隻需要塗色1次，然後我們在(1)的基礎上試圖做減法，當然不可能得到正确答案2！

   但是因為HDU這道題的測試資料沒有能夠發現該錯誤，是以才會有一大堆部落格在介紹這種方法。。。:)

   這種做法的題解一大堆。。都是錯在了這裡。。它們中的幾篇題解連結如下：

       http://blog.csdn.net/libin56842/article/details/9708807

       http://blog.csdn.net/a601025382s/article/details/37737303

  然而，正确的dp方法我還在思考中。。。未完待續

轉載于:https://www.cnblogs.com/AcIsFun/p/5332856.html