网站如何推广行业,社交网站制作,wordpress前台禁止下载文件,域名网址区别Catch That Cow POJ - 3278 这道题我看大家用的方法都是bfs搜索#xff0c;为什么在我看来这就是一个动态规划的题目啊啊啊啊啊啊啊
dp[x]表示从N出发到x所需要的最小时间
那么得到如下转移方程
如果x N的话#xff0c;那么只能通过走路来转移#xff0c;所以dp[x] … Catch That Cow POJ - 3278 这道题我看大家用的方法都是bfs搜索为什么在我看来这就是一个动态规划的题目啊啊啊啊啊啊啊
dp[x]表示从N出发到x所需要的最小时间
那么得到如下转移方程
如果x N的话那么只能通过走路来转移所以dp[x] N - xx N时候
而x N时候可以通过2种方式来转移
1走路转移 dp[x] dp[x-1] 1
2跳跃加走路转移
当x为偶数的时候
dp[x] min(dp[x],dp[x/2]1,dp[x/21]3)
当x为奇数的时候
dp[x] min(dp[x],dp[(x-1)/2]2,dp[(x1)/2]2) 代码 #include iostream
#include algorithm
#include cstdio
using namespace std;
int N,K;
const int MAX 100005;
int dp[MAX];int main(){cinNK;for(int i 0;i K;i){dp[i] abs((int)(N - i));}for(int i N1;i K;i){if(i 1) // 奇数{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[(i1)/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);}}coutdp[K]endl;return 0;
} 补充刚才尝试了一下模拟的方法确实也行的通而且代码量不大 #include iostream
#include cstdio
#include queue
using namespace std;
typedef pairint,int P;
const int MAX 200005;
int used[MAX];
int main(){
int N,K;
cinNK;
queueP Q;
Q.push(make_pair(0,N));
while(!Q.empty()){
P p Q.front();Q.pop();
if(p.second K){
coutp.firstendl;
break;
}
if(p.second K 2 !used[p.second 1]){
Q.push(make_pair(p.first1,p.second 1));
used[p.second 1] 1;
}
if(p.second 1 !used[p.second - 1]){
Q.push(make_pair(p.first1,p.second - 1));
used[p.second - 1] 1;
}
if(p.second * 2 2* K !used[p.second * 2]){
Q.push(make_pair(p.first1,p.second * 2));
used[p.second * 2] 1;
}
}
return 0;
}
