51nod 1693 水群

基准时间限制：0.4 秒 空间限制：524288 KB 分值: 160 难度：6级算法题

 收藏

 关注

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

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

 

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

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

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

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

假设当前对话框中的表情数是num0，剪贴板中的表情数是num1，

那么第一种操作就是num1=num0

第二种操作就是num0+=num1

第三种操作就是num0--

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

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

Input

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

Output

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

Input示例

233

Output示例

17

 

解法一

spfa

知道点电脑的都知道 一直复制相同的东西是无意义的 

所以我们把第一第二种操作看为一种 

而且我们还发现 某个点可以被多个点连接

多次连接耗时太多 

所以我们只需连到他的质数倍就可以了 

经研(ti)究(jie)发现 只有小于等于13的质数才对结果有影响

解法二

dp (来自myj Orz)

屠龙宝刀点击就送

#include <cstring>

#include <cstdio>

#include <queue>

#define N 1000005

using namespace std;

bool notPrime[N],vis[N];

int Prime[N]={,,,,,,,},num,n,dis[N];

void spfa()

{

    queue<int>q;

    q.push();

    memset(dis,0x3f,sizeof(dis));

    vis[]=;

    dis[]=;

    for(int now;!q.empty();)

    {

        now=q.front();q.pop();

        vis[now]=;

        for(int i=;i<=;++i)

        {

            int v=now*Prime[i];

            if(v>n+) break;

            if(v<n+&&dis[v]>dis[now]+Prime[i])

            {

                dis[v]=dis[now]+Prime[i];

                if(!vis[v])

                {

                    vis[v]=;

                    q.push(v);

                }

            }

        }

        if(now>&&dis[now-]>dis[now]+)

        {

            dis[now-]=dis[now]+;

            if(!vis[now-])

            {

                vis[now-]=;

                q.push(now-);

            }

        }

    }

}

void init()

{

    notPrime[]=;

    for(int i=;i<=N-;++i)

    {

        if(!notPrime[i]) Prime[++num]=i;

        for(int j=;j<=num&&i*Prime[j]<=N-;++j)

        {

            notPrime[i*Prime[j]]=;

            if(i%Prime[j]==) break;

        }

    }

}

int main()

{

    scanf("%d",&n);

    //init();

    spfa();

    printf("%d\n",dis[n]);

    return ;

}

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n,dp[],lit;

int main()

{

    cin>>n;

    memset(dp,/,sizeof(dp)),dp[]=;

    for(int i=,v,base;i<=n+;++i)

    {

        base=dp[i];

        for(v=;true;++v)

            if(dp[i+v]+v<=base) base=dp[i+v]+v;

            else break;

        dp[i]=base,++base;

        for(v=;i+v*i<=n+;++v)

            dp[i+v*i]=min(dp[i+v*i],base+v);

    }

    cout<<dp[n];

    return ;

}

dp (Orz myj)