10
22
2015
1

【KMP+DP】 ZHOJ模拟赛34 T1压缩

1397: 【NOIP2014模拟赛No.34】压缩

时间限制: 1 Sec  内存限制: 512 MB

题目描述

我们定义一种压缩方法。首先将字符串分成若干个部分。对于每个部分,我们找出其最短的循环节。每个部分的循环节拼起来就是压缩后的字符串。
给定一个字符串,长度为n。请求出这个字符串可以被压缩成的最短长度。

输入

输入数据仅有一行,包含一个字符串。保证字符串只含有小写英文字母。

输出

输出一行,包含一个整数,代表答案。

样例输入

bababacacac

样例输出

5 

提示

一种可行的方法是 bababa|c|acac,压缩后得到 bacac,长度为 5。


对于 20%的数据,n≤10。

对于 40%的数据,n≤100。

对于 80%的数据,n≤1000。

对于 100%的数据,n≤5000。

 

选拔爆0,233333333

听字符串大师ZNZ讲解以后突然想来水一发

Category: 魔泥赛 | Tags: KMP DP
7
14
2015
0

【斜率优化】HDU 3507

听说是裸的斜率优化,但我还是照着标程写了一遍。

Category: HDU | Tags: DP 斜率优化

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com