CuttingBitString

作者：冯哲 钟知闲

关键字：动态规划

题目简述

给出一个长度为$N$的$01$字符串,要求将其划成最少的段,使得每段里面的串所构成的数都是$5$的幂次。

$1 \leq N \leq 50$

解题思路

令$f_i$表示$1--i$被划成若干$5$的幂次的段最少要被划成多少段,每次枚举一个前面的$j$然后判断中间的那个段是否为$5$的幂次即可。

当然,对于每个$i$,前面合法的解只有$O(\log_{5}(2^N))=O(N)$个,用前缀和,$hash$可以做到更好复杂度。当然由于 $N\le 50$，最简单的做法是直接使用二进制位运算。

时间复杂度$O(N^3)$或$O(N^2)$,空间复杂度$O(N)$.