Kickstart_Copy & Paste

题目传送门,点击即可转向链接

题意大概就是,给你一个字符串,你要以最少的步数来生成这个字符串。步数有三种:
1. 直接在当前字符串后面增加一个字符。
2. 选择一段进行复制,放进复制区。
3. 把复制区的内容加到当前字符串的末尾。

ps: 复制区的内容是会继续保留的,即只要不改复制区的内容,它就一直在。

n<=6直接dfs就好了。
n=100的情况,线上我一开始计算的时候左倾地认为剪枝过的bfs/dfs是可以掐住8分钟的。因此就在各种做优化,比如加一个map或set防止重复的复制等。真是愚蠢的我。太需要学习一个了。

其实是一个非常明显的DP。每个到第i个字符的子串复制区此时都用i^2种可能,因此状态数总共是n^3。注意在复制的时候只有当前是可以复制的时候才可以状态转移,因此时间复杂度是O(n^3 * n) = O(n^4),乘上n是因为判断子串是否可以往下面复制。

另附源代码:

点赞
  1. ohazyi说道:

    test :smile:

发表评论

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