51nod 1693 水群 (spfa)

Description

总所周知,水群是一件很浪费时间的事,但是其实在水群这件事中,也可以找到一些有意思的东西。

比如现在,bx2k就在研究怎样水表情的问题。

首先,bx2k在对话框中输入了一个表情😏,接下来,他可以进行三种操作。

第一种,是全选复制,把所有表情全选然后复制到剪贴板中。

第二种,是粘贴,把剪贴板中的表情粘贴到对话框中。

第三种,是退格,把对话框中的最后一个表情删去。

假设当前对话框中的表情数是num0,剪贴板中的表情数是num1,那么第一种操作就是num1=num0

第二种操作就是num0+=num1

第三种操作就是num0--

现在bx2k想知道,如果要得到n(1<=n<=10^6)个表情,最少需要几次操作。

请你设计一个程序帮助bx2k水群吧。

 

Input

一个整数n表示需要得到的表情数

 

Output

一个整数ans表示最少需要的操作数

 

Input示例

233

 

Output示例

17

 

思路

我们每一次独立的操作无疑就是 复制 1 次 + 粘贴 x 次 + 退格 y 次 ,因为连续复制两次显然无意义,并且退格在粘贴之前与之后都是同样的效果。

于是题目相当于:当前有一个数 $x$ ,操作 $1$ 是 $x=x \times k$ ,代价为 $k$ ;操作 $2$ 是 $x=x-1$ ,代价为 $1$ ,求从 $1$ 到 $n$ 的最小代价。

显然我们可以建图求最短路即为最终的结果,但是 $x=x \times k$ 所生成的边数太多,经过思考我们可以将 $k$ 质因子分解,最终变为 $x=x \times [2,3,5,7...]$ ,这样便消除了其中的冗余边。

经过测试取前 $5$ 个质数就可以保证答案~

 

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
#define inf 0x7f7f7f7f

int prime[]= {2,3,5,7,11};

bool vis[N];
int dist[N];
int n,maxn;

int spfa(int s,int e)
{
    queue<int> sk;
    maxn = n+10;
    for(int i=0; i<maxn; i++)
    {
        dist[i] = inf;
        vis[i] = false;
    }
    dist[s] = 0;
    vis[s] = true;
    sk.push(s);
    while(!sk.empty())
    {
        int u = sk.front();
        sk.pop();
        vis[u] = false;
        if(u-1>0&&dist[u-1]>dist[u]+1)
        {
            dist[u-1] = dist[u] + 1;
            if(!vis[u-1])
            {
                vis[u-1] = true;
                sk.push(u-1);
            }
        }
        for(int i=0; i<5&&prime[i]*u<maxn; i++)
        {
            int to = prime[i]*u;
            int cost = prime[i];
            if(dist[to]>dist[u]+cost)
            {
                dist[to] = dist[u]+cost;
                if(!vis[to])
                {
                    vis[to]=true;
                    sk.push(to);
                }
            }
        }
    }
    return dist[e];
}


int main()
{
    scanf("%d",&n);
    printf("%d\n",spfa(1,n));
    return 0;
}