【動態規劃BFS】相遇

這是我第一次模擬題測試點全部AC。。。

同機房的DALAO都用的BFS

然而我用的DP（其實不會BFS）

---

?

話不多說，上題！

（灰常詳細）DP解法：

重點還是狀態轉移方程式的推導

1個點i要么是后面的位置i-1往前走一步，i+1往后走一步即dg[i]=

或者是一個點i*2從i瞬移一步。

如果是自身的話也可能不走。

此時就要找哪一種走的最少了

狀態轉移方程就是dg[i]=min(dg[i],min(dg[i-1]+1,dg[i+1]+1))

和dg[i*2]=min(dg[i*2],dg[i]+1)

推導出方程就比較容易解了

#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[2000005];//數組開兩倍是因為有可能走到K點后面再往前走。
int main()
{freopen("meet.in","r",stdin);freopen("meet.out","w",stdout);int N,K;scanf("%d%d",&N,&K);memset(dp,0x7f,sizeof(dp));//將所有數初始化到最大值dp[N]=0;//從N開始，步數為0for(int i=N-1;i>=0;i--)//先往前推，把前面的步數通過dp[N]算出來；{dp[i]=min(dp[i],(dp[i-1]+1,dp[i+1]+1));dp[i*2]=min(dp[i*2],dp[i]+1);}for(int i=N;i<=K;i++)//再往后推，計算后面的步數。{dp[i]=min(dp[i],min(dp[i-1]+1,dp[i+1]+1));dp[i*2]=min(dp[i*2],dp[i]+1);}cout<<dp[K];    //打印K點的步數。return 0;        
}

看起來還是挺簡單的

我再去研究一下廣搜做法。。。

?