[問題] ICPC題目請益

看板Prob_Solve作者flere (人間失格)時間12年前 (2012/07/22 18:01)推噓3(3推 0噓 3→)

留言6則, 4人參與討論串1/1

想問一下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

→

bleed1979

07/22 23:44, , 1^F

07/22 23:44, 1^F

→

bleed1979

07/23 00:01, , 2^F

07/23 00:01, 2^F

打錯年份了> <....最近在積極練習中> < 有需要的可以看一下以下的題目直連 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)

推

DJWS

07/23 11:10, , 3^F

07/23 11:10, 3^F

推

dreamoon

07/24 20:09, , 4^F

07/24 20:09, 4^F

推

kkbbs

07/28 22:42, , 5^F

07/28 22:42, 5^F