[問題] ICPC題目請益

[flere (人間失格)]

想問一下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:可以直接給題目嗎？拉丁美洲分南美和墨西哥兩區
→ bleed1979:我找到該題了在regional 2009的拉丁美洲，這年只有一區
打錯年份了> <....最近在積極練習中> <
有需要的可以看一下以下的題目直連

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:http://uva.onlinejudge.org/external/121/12188.html
推 dreamoon:dp
推 kkbbs:MST
→ kkbbs:阿 看錯= =