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]={0,2,3,5,7,11,13,19},num,n,dis[N];
void spfa()
{
    queue<int>q;
    q.push(1);
    memset(dis,0x3f,sizeof(dis));
    vis[1]=1;
    dis[1]=0;
    for(int now;!q.empty();)
    {
        now=q.front();q.pop();
        vis[now]=0;
        for(int i=1;i<=7;++i)
        {
            int v=now*Prime[i];
            if(v>n+20) break;
            if(v<n+20&&dis[v]>dis[now]+Prime[i])
            {
                dis[v]=dis[now]+Prime[i];
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v); 
                }
            }
        }
        if(now>0&&dis[now-1]>dis[now]+1)
        {
            dis[now-1]=dis[now]+1;
            if(!vis[now-1])
            {
                vis[now-1]=1;
                q.push(now-1); 
            }
        }
    }
}
void init()
{
    notPrime[1]=1;
    for(int i=2;i<=N-5;++i)
    {
        if(!notPrime[i]) Prime[++num]=i;
        for(int j=1;j<=num&&i*Prime[j]<=N-5;++j)
        {
            notPrime[i*Prime[j]]=1;
            if(i%Prime[j]==0) break;
        }
    }
}
int main()
{
    scanf("%d",&n);
    //init();
    spfa();
    printf("%d
",dis[n]);
    return 0;
}

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
int n,dp[1000045],lit;
int main()
{
    cin>>n;
    memset(dp,127/3,sizeof(dp)),dp[1]=0;
    for(int i=1,v,base;i<=n+40;++i)
    {
        base=dp[i];
        for(v=1;true;++v)
            if(dp[i+v]+v<=base) base=dp[i+v]+v;
            else break;
        dp[i]=base,++base;
        for(v=1;i+v*i<=n+40;++v)
            dp[i+v*i]=min(dp[i+v*i],base+v);
    }
    cout<<dp[n];
    return 0;
}