Catch That Cow

? POJ - 3278?

這道題我看大家用的方法都是bfs搜索，為什么在我看來這就是一個(gè)動(dòng)態(tài)規(guī)劃的題目啊啊啊啊啊啊啊

dp[x]表示從N出發(fā)到x所需要的最小時(shí)間

那么得到如下轉(zhuǎn)移方程

如果x < N的話，那么只能通過走路來轉(zhuǎn)移，所以dp[x] = N - x，x <= N時(shí)候

而x > N時(shí)候，可以通過2種方式來轉(zhuǎn)移

（1）走路轉(zhuǎn)移 dp[x] = dp[x-1] + 1

（2）跳躍加走路轉(zhuǎn)移

當(dāng)x為偶數(shù)的時(shí)候

dp[x] = min(dp[x],dp[x/2]+1,dp[x/2+1]+3)

當(dāng)x為奇數(shù)的時(shí)候

dp[x] = min(dp[x],dp[(x-1)/2]+2,dp[(x+1)/2]+2)

代碼：

#include <iostream> #include <algorithm> #include <cstdio> using namespace std; int N,K; const int MAX = 100005; int dp[MAX];int main(){cin>>N>>K;for(int i = 0;i <= K;i++){dp[i] = abs((int)(N - i));}for(int i = N+1;i <= K;i++){if(i & 1) // 奇數(shù){dp[i] = min(dp[i],dp[(i-1)/2]+2);dp[i] = min(dp[i],dp[i-1]+1);dp[i] = min(dp[i],dp[(i+1)/2]+2);} else{dp[i] = min(dp[i],dp[i/2]+1);dp[i] = min(dp[i],dp[i-1]+1);dp[i] = min(dp[i],dp[i/2 + 1]+3);}}cout<<dp[K]<<endl;return 0; }

補(bǔ)充：剛才嘗試了一下模擬的方法，確實(shí)也行的通，而且代碼量不大

#include <iostream> #include <cstdio> #include <queue> using namespace std; typedef pair<int,int> P; const int MAX = 200005;? int used[MAX]; int main(){ int N,K; cin>>N>>K; queue<P> Q; Q.push(make_pair(0,N)); while(!Q.empty()){ P p = Q.front();Q.pop(); if(p.second == K){ cout<<p.first<<endl; break; } if(p.second <= K + 2 ?&& !used[p.second + 1]){ Q.push(make_pair(p.first+1,p.second + 1)); used[p.second + 1] = 1; } if(p.second >= 1 && !used[p.second - 1]){ Q.push(make_pair(p.first+1,p.second - 1)); used[p.second - 1] = 1; } if(p.second * 2 <= 2* K ?&& !used[p.second * 2]){ Q.push(make_pair(p.first+1,p.second * 2)); used[p.second * 2] = 1; } } return 0; }

總結(jié)

以上是生活随笔為你收集整理的动态规划训练13 [Catch That Cow poj3278]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。