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

請你設計一個程序幫助bx2k水群吧。

出題人的解題報告：首先簡化題目，題面的意思就是，當前有一個數s 操作1是s*=k代價為k，操作2是s--代價為1 求把s從1變到n的最小代價
做法1： 直接暴力記憶化搜索，F(i)表示從1到i用的最小操作數 則F(i)=min(F(i+1),min{F(k)+n/k|n%k==0}) 當然這樣做肯定過不了 做法2： 考慮把問題轉換成圖論模型，對于每個i 連邊i→i-1邊權為1，連邊i→i*k邊權為k 那么題目就是要求點1到點n的最短路 但是很顯然這樣復雜度還是很高并不能過 做法3： 注意到如果一條邊i→i*k能用若干條邊代替 那么i→i*k這條邊就是沒有意義的 因為那些邊的權值的乘積等于k 即那些邊的權值和小于等于k 因此對于每個i，只用連i→i*p的邊，其中p是質數 這樣就可以讓邊數變得很小了 但是0.1s還是過不去 做法4： 既然過不去，就可以想一些別的辦法 考慮在做法3中記錄每一個點的最短路路徑 就是打一個每個點自己最短路上的上一個點的表 那么可以從表中發現，i→i-1的邊不會連續出現4次以上 而且i→i*p的邊只有當p<=13的時候才有意義 于是又可以刪掉很多邊，邊數大概是3*10^6條 但是這樣做復雜度還是不夠，用時稍微多于0.1s 做法5： 既然最短路的做法復雜度太高，就可以再換個思路。 重新考慮記憶化搜索的做法，F(i,j)表示從1到i上一條邊的狀態是j的最少操作數 j=0時上一條邊可以是i→i-1的，否則就是i→i*p的邊 那么F(i,0)=min(min{F(i+k,1)|0<k<5},min{F(i/p,0)|p<13}) 于是這樣做就可以把時間降到最低，從而做出此題
最短路徑做法

#include<iostream> #include<stdio.h> #include<queue> using namespace std; const int inf=0x3f3f3f3f; const int maxn=1e6+20; int n,ans[maxn],a[]={2,3,5,7,11,13}; bool vis[maxn]; queue<int> q; void spfa(){q.push(1);vis[1]=1;while(!q.empty()){int cur=q.front();q.pop();vis[cur]=0;for(int i=0;i<6;i++){if(cur*a[i]<n+20&&ans[cur*a[i]]>ans[cur]+a[i]){ans[cur*a[i]]=ans[cur]+a[i];if(!vis[cur*a[i]]) q.push(cur*a[i]),vis[cur*a[i]]=1;}}if(ans[cur-1]>ans[cur]+1){ans[cur-1]=ans[cur]+1;if(!vis[cur-1]) q.push(cur-1),vis[cur-1];}} } int main(){scanf("%d",&n);for(int i=2;i<=n+20;i++) ans[i]=inf,vis[i]=0;spfa();printf("%d\n",ans[n]); } 記憶化搜索

#include<iostream> #include<stdio.h> #include<queue> #include<algorithm> using namespace std; const int inf=0x3f3f3f3f; const int maxn=1e6+20; int n,ans[maxn][2],a[]={2,3,5,7,11,13}; queue<int> q; int s(int n,int way){if(n==1) return 0;if(ans[n][way]) return ans[n][way];ans[n][way]=inf;for(int i=0;i<6;i++)if(n%a[i]==0) ans[n][way]=min(ans[n][way],s(n/a[i],1)+a[i]);if(!way) return ans[n][way];ans[n][0]=ans[n][1];for(int i=1;i<5;i++)ans[n][way]=min(ans[n][way],s(n+i,0)+i);return ans[n][way]; } int main(){scanf("%d",&n);printf("%d\n",s(n,1)); }

總結

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

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