Deep_Kevin的娱乐空间

正题动态规划的基本思路找出某种可以描述当前状态的方法，并且通过合理的转移与状态的压缩，在满足无后效性和无转移环的情况下得出所求状态的解。简单动态规划1.记忆化搜索的基本方法2.常见的动态规划模型3.背包4.区间Dp5.LIS LCS 回文6.树上Dp7.数位Dp8.状态压缩Dp上述算法在我的博文或者其他一些博主的博文中可以快速学习，在此不再赘述。在动态规划时需考虑状态的数量，转移的数量与状态转移是否可能形成闭环。如果有其一不满足那么就需要重新设计状态，优化转移速度或改变转移方式。

正题 考虑构造Dp:表示当前在第i行,第j列的轮廓线上,上一行匹配成功的结束端点集合为S,当前这行匹配k了模板第一行的k个,第二行的l个 考虑到集合S实际上只用记录有效的位置,也就是pos>=c,那么总状态数就是 转移枚举后一个位置放什么,用kmp来找第i个位置后面放一个x会转移到哪里,kmp的时间复杂度显然正确 若当前第二行新加进来一个字符满足第二行匹配c位,且S中第一位为1,那么这个状态就不合法,直接跳过. 否则也要更新S,将第一位弹掉,...