想问一下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)