想問一下ICPC 2009拉丁美洲賽區的第三題 題目大意是給一個長度最多到1000的字串 你可以把她想像成一個"鎖"目前的狀態 然後可以去轉她,問說從給定的狀態轉成全部都是"a"要幾步 z往上轉就變成a a往下轉就變成z 然後相鄰的可以一起轉算一步 比如說bbbb -> aaaa就只要一步 一開始想到greedy的作法 可是"n"的位置剛好在正中間 有可能往上轉也有可能往下> < 就算是一開始比較靠近a的也不見得就是往下轉到a 比如說mno這一串 如果因為m往下轉到a比較近,往上經過z到a比較遠就往下轉的話 就會比較慢 因為我們可以三個全部都一起往上轉 變成xyz後 再多花3步就可以變成aaa了!!> < 是否有人可以提供個解題方向??> < 感覺不是greedy> < 最短路徑的話不知道如何作圖OAQ DP的話感覺最有可能....可是想不到轉移方程>"< 希望給點提示!! 感謝: ) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.195.203.24 打錯年份了> <....最近在積極練習中> < 有需要的可以看一下以下的題目直連 http://ppt.cc/OQuz ※ 編輯: flere 來自: 123.195.203.24 (07/23 07:24) ※ 編輯: flere 來自: 123.195.203.24 (07/23 07:25) ※ 編輯: flere 來自: 123.195.203.24 (07/23 07:26)