文档章节

SPOJ:Strange Waca(不错的搜索&贪心&剪枝)

o
 osc_z1hvg4cu
发布于 2018/04/24 20:35
字数 593
阅读 25
收藏 0

Waca loves maths,.. a lot. He always think that 1 is an unique number. After playing in hours, Waca suddenly realize that every integer can be represented by digit '1', plus operator and minus operator. For example, 1534 can be represented as 1111 + 1 + 111 + 111 - 11 - 11 + 111 + 111. In that case, there are total 7 operators (plus and minus).

Now, Waca wants to know, what is the minimum number of operators needed to achieve X

Input

First row is an integer T, the number of test cases.
Next T rows will each contain an integer, X, the number given to Waca

Output

For each test cases, print an integer, the minimum number of operators needed to achieve X.

Example

Input:
2
1534
219 Output: 7
4

Constraints:

  • 1 ≤ T ≤ 10
  • 1 ≤ X ≤ 1012

题意:现在给定一个数N,问最小可以用多少个只含1的数表示出来,输出最小运算次数。比如219=111+111-1-1-1(4=3加+1减)

思路:首先先尝试贪心,发现没有什么必定的转发法则,而且每种只含1的数出现次数不超过10,而且不可能出现几次正几次负,因为这样都不是最优的。

           所以用搜索来解决,再加一些剪枝。

           搜索:对于当前数N,有三种去向:(以下X只含1,而且位数和N相同,如N=234,X=111;N=4324,X=1111;)

                          1,减若干个X,使得N-cnt1*X刚好大于等于0;  

                          2,减若干个X,使得N-cnt2*X刚好小于等于0;

                          3,用比N高一位的X,减去N。

          剪枝:这样最坏的情况下复杂度是O(T*10*3^12)=5*1e7(其中10是算位数),有些高,注意到第三种情况可以剪枝。假定N有L位,N小于当前5*10^L时,X-N>5*10^L,只会使情况更坏(其中X含L+1个1)

          这样的最坏情况是O(T*10*2.5^12)=5*1e6。再加上次数限制的剪枝,肯定就没有问题了。

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll base[]={0,1,11,111,1111,11111,111111,1111111,11111111,111111111,
           1111111111,11111111111,111111111111,1111111111111};
ll ans;
void dfs(ll N,ll times){    
    if(times>ans) return;
     if(N==0){ if(ans>times) ans=times;return ;}    
    ll tmp=N,L=0;
    while(tmp){ L++; tmp/=10;}
    if(N/base[L]) dfs(N-(N/base[L])*base[L],times+N/base[L]);    //避免死循环    
    dfs((N/base[L]+1)*base[L]-N,times+N/base[L]+1);
    if(N>=(base[L+1]-base[L])/2)dfs(base[L+1]-N,times+1);  //剪枝 
}
int main()
{
    int T; ll N; cin>>T;
    while(T--){
        ans=100000000;
        scanf("%lld",&N);
        dfs(N,0);
        printf("%lld\n",ans-1);
    }
    return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Vue+Spring Data JPA+MySQL 增查改删

视频讲解: https://www.bilibili.com/video/BV16i4y1G7i2/ 工程概述: 前后端分离,进行简单增查改删(CRUD) 前端使用VUE 后端使用Spring Data JPA 数据库使用MySQL #EmployeeController.jav...

潘文海
30分钟前
13
0
我花了一个星期,做出了公司的管理系统,只需几个步骤!

我是企业的管理人员,公司发展到现阶段,感觉进入到了瓶颈期,每个员工的工作都已经饱和,很难再挤出时间做其它的事情,需要一款合适的管理软件来协作我们的工作。本来打算买一套管理软件就行...

科技那些事儿
35分钟前
19
0
如何从Android应用程序获取崩溃数据? - How do I obtain crash-data from my Android application?

问题: How can I get crash data (stack traces at least) from my Android application? 如何从我的Android应用程序获取崩溃数据(至少是堆栈跟踪)? At least when working on my own de......

技术盛宴
45分钟前
16
0
使用telnet测试指定端口的连通性

大家好,我是良许。 大家知道,telnet 是一个阉割版的 ssh ,它数据不加密,数据容易被盗窃,也容易受中间人攻击,所以默认情况下 telnet 端口是必须要被关闭的。 telnet为用户提供了在本地计...

良许Linux
49分钟前
13
0
创建python项目-从0到1开始Django第二篇

接上一篇:基于Centos7系统Django环境搭建-从0到1开始Django第一篇 https://my.oschina.net/guiguketang/blog/4333406 1.项目初始化 #django-admin startproject mysite 2.启动服务,执行man...

硅谷课堂
58分钟前
29
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部