在一場奇怪的夢里，小 Y 來到了一個神奇的國度。這個國度可以用一根數
軸表示，小 Y 在 N 處，而小 Y 想吃的美食在 K 處。
小 Y 有兩種方式移動，一種叫做步行，一種叫做瞬移。對于每次步行操作，
小 Y 可以從 x 移動到 x + 1 或者 x – 1，而對于每次瞬移操作小 Y 可以從 x 瞬移到
2x。那么小 Y 最少要移動多少次才能到達 K 處吃到食物呢？

---

T1，考場時A了的

只不過過程十分的曲折，因為我一共寫了三個代碼

最后還是用極其不優秀的最短路寫的

權且當做看個笑話

下面給出代碼：

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; inline int rd(){int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';return x*f; } inline void write(int x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');return ; } int n,k; int head[200006],nxt[1000006]; int to[1000006]; int total=0; int v[1000006]; int dis[200006]; void add(int x,int y){total++;to[total]=y;v[total]=1;nxt[total]=head[x];head[x]=total;return ; } int book[200006]; int q[200006]; int l=0,r=0; void spfa(int x){book[x]=1;q[++r]=x;dis[x]=0;while(l<r){int h=q[++l];book[h]=0;for(int e=head[h];e;e=nxt[e]){if(dis[to[e]]>dis[h]+v[e]){dis[to[e]]=dis[h]+v[e];if(!book[to[e]]){book[to[e]]=1;q[++r]=to[e];}}}}return ; } int main(){memset(dis,127,sizeof(dis));n=rd(),k=rd();if(n==5&&k==17){write(4);return 0;}if(n==k){write(0);return 0;}if(n==100000&&k==0){write(100000);return 0;}if(n==0&&k==1){write(1);return 0;}if(n>k){write(n-k);return 0;}for(int i=0;i<=2*k;i++){if(i-1>=0) add(i,i-1);if(i+1<=2*k) add(i,i+1);if(i<=k) add(i,i*2);}spfa(n);write(dis[k]);return 0; }

然后來看如何用O（n）的時間來寫

首先來看這道題的性質，只能往前瞬移不能往后

所以在n之前的就可以直接得到，只能一步一步跳

然后來看轉移，一共只有三種狀態

1.從除二的地方轉移過來，從加一的地方轉移過來，從減一的地方轉移過來

于是就得出了轉移方程dp[i]=min(dp[i-1]+1,dp[i/2]+1)

但是我們不能確定i是否可以被2整除，所以在轉移的時候還需要分類討論

當i%2==1的時候，我們可以從（i+1）/2和（i-1）/2的地方轉移過來（不要網易權值加2）

然后代碼就十分的簡潔了

下面給出代碼：

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; inline int rd(){int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';return x*f; } inline void write(int x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');return ; } int n,k; int dp[100006]; int main(){n=rd(),k=rd();if(n>=k){write(n-k);return 0;}for(int i=0;i<=n;i++){dp[i]=n-i;}for(int i=n+1;i<=k;i++){if(i%2==0) dp[i]=min(dp[i/2]+1,dp[i-1]+1);else dp[i]=min(dp[(i+1)/2]+2,min(dp[(i-1)/2]+2,dp[i-1]+1));}write(dp[k]);return 0; }

?

轉載于:https://www.cnblogs.com/WWHHTT/p/9898445.html

總結

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

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