JLOI2008 CODES

一天半,唉。。真该AFO了。

首先考虑我们可以DP,设状态 dp[i][j] 表示 第 i 个字符串  还需要匹配长度为 j 的前缀   可以得到的最短答案。

转移:

转移就是枚举一个字符串 i_0 来与之匹配。记忆化搜索非常好写。注意讨论两种情况:

  1. i_0比当前前缀长
  2. i_0比当前前缀短

用 dp[i0][?] + 匹配长度 去更新dp[i][j]。(?是因为我懒得讨论了……代码里有)

数据范围很小,暴力匹配即可。

注意事项:

第一个细节就是字符串可以重复利用;

第二个细节是让dp[i][0]=0 其余为 +\infty

第三个细节就是最后统计答案和DP过程中别忘记比较字典序。

字典序:

 answ[i][j] 保存当前 dp[i][j] 对应的具体方案,

更新 dp[i][j] 顺便更新 answ[i][j] 即可。

每次遇到 dp[i0][?]+len  dp[i][j] 相等的情况,判定字典序,然后更新 answ[i][j] 即可。

最后的答案是 dp[i][len[i]]

O(\text{跑得过})

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据