logo
publist
写文章

简介

该用户还未填写简介

擅长的技术栈

可提供的服务

暂无可提供的服务

UVA11022 String Factoring(kmp+字符串周期+区间dp)

用f[i][j]用来表示[ i, j ]区间中合并之后的最小长度,那么显然f[1][n]就是答案。dp有两种转移方式:1.两个区间的答案合并:2.考虑[ i, j ]这个区间内部合并(可能是两个合并,也可能是3个、4个....相同的循环节合并)这部分稍微难一些,我们回想一下kmp里学过的,如果len%(len-ne[r])==0,那么len-ne[r]就是最小的循环节长度!

#动态规划#算法
到底了