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

思路

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

于是题目相当于：当前有一个数 x ，操作 1 是 x=x×k ，代价为 k ；操作 2 是 x=x−1 ，代价为 1 ，求从 1 到 n

显然我们可以建图求最短路即为最终的结果，但是 x=x×k 所生成的边数太多，经过思考我们可以将 k 质因子分解，最终变为 x=x×[2,3,5,7...]

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

AC 代码

#includeusing namespace std;const int N = 1e6+10;#define inf 0x7f7f7f7fint prime[]= {2,3,5,7,11};bool vis[N];int dist[N];int n,maxn;int spfa(int s,int e){ queue sk; maxn = n+10; for(int i=0; i0&&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]*udist[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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。