POJ-3278

2020-04-01 16:01:25来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

POJ-3278

刚开始做这道题时,直接上了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.cnblogs.com/youngbai/p/12615260.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:津津的储蓄计划 NOIp提高组2004

下一篇:排序算法之快速排序代码c++