剛開始做這道題時，直接上了bfs，但是奈何剪枝寫的不好，秒TLE，但是這道題真的沒有那么難以克服，于是就換了個思路，使用dp很順利的解決了這道題，
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m;
int dp[200010];
int main(){
cin>>n>>m;
//dfs(n,0);
if(n>=m){ //特判，因為如果n>=m,農夫的坐標只能一個一個的減小，所以這種情況很平凡，
cout<<n-m;
return 0;
}
//初始化1-n以及n-m
for (int i=1;i<=n;i++){
dp[i]=n-i;
}
for (int i=n+1;i<=m;i++){
dp[i]=10000;
}
for(int i=n+1;i<=m;i++){
dp[i]=min(dp[i],dp[i-1]+1);
if(i%2==0){
dp[i]=min(dp[i],dp[i/2]+1);
}
if(i%2==1){
dp[i]=min(dp[i],dp[i/2]+2); //其實這部是多余的，因為dp[i/2]肯定大于dp[i/2+1];
dp[i]=min(dp[i],dp[i/2+1]+2);
}
}
cout<<dp[m];
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/44993.html
標籤：C++
下一篇：排序演算法之快速排序代碼c++