51nod 1693 水群(spfa最短路)

本文主要是介绍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

解题思路

可以结合题意先思考一个简单问题，对于A=B*k，如果将一个数B转化为A满足这样一个等式，就可以将B复制一次，然后粘贴k-1次，一共操作k次，这样从B便可延伸出k-1个分支，当然这并不是简单的优化。对于数$k=p1*p2*p3*……(pi为质因子)$，这样就可以先将B复制一次粘贴p1-1次，然后将(B*p1)复制一次粘贴p2-1次，这样分支数便减少为(p1+p2+p3+……)；但是还存在一种情况，就是对p进行质因子分解的时候只需要2，3，5，7，11这样前5个即可，原因大概就是例如$46=2*23$，但是$23=24-1=2*2*2*3-1$，即将23步优化为了10步，所以在扩展时只扩展 $B*2,B*3,B*5,B*7,B*11$这样五个节点即可，另外对应退格键的分支是B-1。根据这种扩展规则进行建图，求1-n的最短路即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 1000007
bool vis[maxn];
int dis[maxn],n;
int a[]={2,3,5,7,11};
void spfa()
{memset(vis,0,sizeof(vis));memset(dis,INF,sizeof(dis));queue<int>qu;qu.push(1);vis[1]=1;dis[1]=0;while(!qu.empty()){int t=qu.front();qu.pop();vis[t]=0;if(t-1>0&&dis[t-1]>dis[t]+1){dis[t-1]=dis[t]+1;if(!vis[t-1]){qu.push(t-1);vis[t-1]=1;}}for(int i=0;i<5;i++){if(t*a[i]<maxn&&dis[t*a[i]]>dis[t]+a[i]){dis[t*a[i]]=dis[t]+a[i];if(!vis[t*a[i]]){qu.push(t*a[i]);vis[t*a[i]]=1;}}}}printf("%d\n",dis[n]);
}
int main()
{scanf("%d",&n);spfa();return 0;
}

这篇关于51nod 1693 水群(spfa最短路)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---