大意: 初始有一个空串, 操作(1)在开头或末尾添加一个字符. 操作(2)在开头或末尾添加该串的逆串. 求得到串$S$所需最少操作数.

显然最后一定是由某个偶回文通过添加字符得到的, 那么只需要求出所有偶回文的最少操作数即可.

结论: 偶回文最后一次进行翻倍操作一定最优.

证明考虑数学归纳, 对于长为$2$的回文串显然成立.

对长度$>2$的偶回文串$A$, 记最后一次翻倍得到的串$B$, $B$的一半为$C$.

记$f(S)$为串$S$的最优值, 就有$f(B)=f(C)+1$.

考虑由$B$得到$A$的过程, 有$4$种情况:

$1.$ $A=B$, 那么结论成立.

$2.$ 同时在$B$的左端和右端添加字符. 那么$B$只能是由$A$去掉左右两端得到的串. 总操作数是$f(C)+3$, 在$C$一端添加一个字符再翻倍操作数为$f(C)+2$更优, 所以这种情况不成立.

$3.$ 全部在$B$的左端添加字符. 那么$B$只能是$A$的最长偶回文后缀, 总操作数就为$f(C)+|A|-|B|+1$. 而在$C$的左侧添加字符然后再翻倍的操作数为$f(C)+\frac{|A|}{2}-\frac{|B|}{2}+1$更优, 所以不成立.

$4.$ 全部在$B$的右端添加字符. 同情况$3.$

最新文章

1. 【第四篇】ASP.NET MVC快速入门之完整示例（MVC5+EF6）
2. Lua 学习笔记（八）错误（error）
3. 汇编语言进阶和Makefile进阶---第二天
4. Display HTML in WPF and CefSharp
5. [转]Python程序员必须知道的30条编程技巧
6. 标准C IO函数和 内核IO函数 效率（时间）比较
7. [CareerCup] 9.5 Permutations 全排列
8. Android设计画面中有EditText时取消启动时自动获得焦点调用系统输入法的方法
9. 如何保护java程序不被反编译
10. 消息系统Flume与Kafka的区别
11. Java中的异常处理机制的简单原理和应用
12. 精通 Oracle+Python，第 3 部分：数据解析
13. 如何学习YII
14. Bootstrap-table使用记录（转）
15. ubantu 安装 wget
16. 如何快速学好Shell脚本？
17. [CENTOS7] 加入Windows域
18. 【Markdown】Markdown相关问题
19. Select 、Poll 和 Epoll
20. BZOJ 1066：[SCOI2007]蜥蜴（最大流)

热门文章

1. ZR#955 折纸
2. MySQL个人用户的安装配置详解
3. HTTP_POST请求的数据格式
4. 第11组 Alpha冲刺（4/6）
5. spaCy 第二篇：语言模型
6. win10系统在执行“ vagrant box add centos7 vagrant-centos-7.box”添加box时，报错“Vagrant failed to initialize at a very early stage: Failed to locate the powershell executable on the available PATH. ”
7. Spring事务知识点
8. CCF认证历年试题
9. GradientDrawable
10. kotlin之MutableMap委托