1693 水群

總所周知，水群是一件很浪費時間的事，但是其實在水群這件事中，也可以找到一些有意思的東西。
比如現在，bx2k就在研究怎樣水表情的問題。
首先，bx2k在對話框中輸入了一個表情，接下來，他可以進行三種操作。
第一種，是全選復制，把所有表情全選然后復制到剪貼板中。
第二種，是粘貼，把剪貼板中的表情粘貼到對話框中。
第三種，是退格，把對話框中的最后一個表情刪去。
假設當前對話框中的表情數是num0，剪貼板中的表情數是num1，
那么第一種操作就是num1=num0
第二種操作就是num0+=num1
第三種操作就是num0–
現在bx2k想知道，如果要得到n(1<=n<=10^6)個表情，最少需要幾次操作。
請你設計一個程序幫助bx2k水群吧。

輸入

一個整數n表示需要得到的表情數

輸出

一個整數ans表示最少需要的操作數

輸入樣例

233

輸出樣例

17

簡述

這個題出的真的巧妙，說實話，我最開始是沒想到是拿最短路寫的。
一個數x，操作1是x?=k代價為k，操作2是x??代價為1，求把x從1變到n的最小代價。

代碼實現

#include <cstdio> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <algorithm> #include <queue> #include <map> #include <vector>#define inf 0x7fffffff using namespace std; const int maxn = 1e6 + 10; int n; // 距離 int dis[maxn]; // 是否在隊列 int vis[maxn]; int p[6] = {2, 3, 5, 7, 11, 13};void init() {for (int i = 0; i < maxn; i++) {dis[i] = inf;vis[i] = 0;} }void spfa(int u) {init();dis[u] = 0;vis[u] = 1;queue<int> q;q.push(u);while (!q.empty()) {u = q.front();vis[u] = 0;q.pop();for (int i = 0; i < 6; i++) {if (u * p[i] < n + 4 && dis[u * p[i]] > dis[u] + p[i]) {dis[u * p[i]] = dis[u] + p[i];if (!vis[u * p[i]]) {vis[u * p[i]] = 1;q.push(u * p[i]);}}}if (dis[u - 1] > dis[u] + 1) {dis[u - 1] = dis[u] + 1;if (!vis[u - 1]) {vis[u - 1] = 1;q.push(u - 1);}}} }int main() {cin >> n;spfa(1);cout << dis[n] << endl;return 0; }

總結

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

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