CF440C 题解

· · 题解

题目大意

给定一个 n，需要把 n 用若干个用 1 组成的数通过加和减表示出来，求最少需要用的 1 的个数。

例：121=111+11-1

所以用了 6 个 1 (n \leq 10^{15})。

具体思路

这道题表面看上去挺难（因为 n \leq 10^{15})，但仔细思考就会发现，在 10^{15} 内，仅包含 1、11、111、1111 等 15 个数。

所以我们可以想到深搜！由于这题的性质，每次搜肯定能得到一个解，然后之后搜的时候如果 1 的数量大于这个解，就可以跳出，怒剪了一大波枝。（最优性剪枝）

也就是从最高位开始，慢慢把位数削成 0。因为把第 i 位消除成 0 后，可以选择数保证这一位不会再变回 1，我们可以一位一位削下去。

深搜只有两种方向，例如第 i 位是 x，

  1. 第一种方向是就是搞 x 个 1 把它削了；

  2. 另一种是搞一堆 1 把它加上去，然后搞一个比前面那个位数多一位的 1 把它再削掉。

这两种都有可能，而其他的方法都不如这两种。

所以哐哐哐就是搜啦！

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans,len;
ll one[17]={0,1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,11111111111,111111111111,1111111111111,11111111111111,111111111111111,1111111111111111};
void dfs(ll x,int sum)
{
    int a,b;
    if(sum>=ans) 
        return;//如果1的数量大于这个解，就可以跳出
    if(x==0)//搜索到边界 
    {
        ans=sum;
        return;
    }
    if(x<0) 
        x=-x;
    //从最高位开始，慢慢把位数削成0
    ll y=x;
    int t=0;
    while(y) 
    {
        t++;
        y/=10;
    }
    ll reta=x;
    ll retb=one[t+1]-x;
    ll h=pow(10,t-1);
    int sa=0,sb=t+1;
    while(reta>=h) 
        reta-=one[t],sa+=t;
    while(retb>=h) 
        retb-=one[t],sb+=t;
    //两种方向，一种加，一种减 
    dfs(reta,sum+sa);
    dfs(retb,sum+sb);
    return;
}

int main()
{
    ll x;
    while(scanf("%lld",&x)!=EOF)//如果没有输入完毕，就继续输入
    {
        ans=1e9;//将ans初始化为极大值 
        dfs(x,0);//开始搜索
        printf("%d\n",ans);
    }
    return 0;
}