首页 > 代码库 > Hihocoder #1527 : 快速乘法 DP
Hihocoder #1527 : 快速乘法 DP
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
在写代码时,我们经常要用到类似 x × a 这样的语句( a 是常数)。众所周知,计算机进行乘法运算是非常慢的,所以我们需要用一些加法、减法和左移的组合来实现乘一个常数这个操作。具体来讲, 我们要把 x × a 替换成:(x<<a0) op1 (x<<a1) op2 (x<<a2) ... opn (x<<an) 这样的形式,其中opi 是+或者-。
举个例子:x × 15 = (x<<4) - (x<<0)。
在本题中,假设左移(包括左移0)和加法、减法所需要的时间都是一个单位的时间,上述的例子所需要的时间是3。
现在给定常数 a 的二进制形式,求实现 x × a 最少需要多少单位的时间。
输入
一个01串,表示 a 的二进制形式,从左到右分别是从高位到低位。
0 < 01串的长度之和 ≤ 106。
a > 0。
输出
输出一个数,表示最小需要多少单位的时间可以实现 x × a。
- 样例输入
1111
- 样例输出
3
Hihocoder #1527 : 快速乘法 DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。