刚开始做这道题时，直接上了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; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/599928.html