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<script type="math/tex" id="MathJax-Element-13">5</script> 個質數就可以保證答案～

?

AC 代碼

#include<bits/stdc++.h> using 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<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; }

總結

以上是生活随笔為你收集整理的51nod 1693 水群 （spfa）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。