首页 > 代码库 > BestCoder Round #89 1002 Fxx and game
BestCoder Round #89 1002 Fxx and game
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5945
分析：
很容易想到用bfs，然而会超时，几乎是O(xt)了
这里用单调队列优化，
首先反着来，f[x] 为 x 要到1 的步数，f[1] = 0;
1、第一个条件就是 队列里面的元素个数小于t，
2、单调队列是个单调递减的队列。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int maxn = 1000000 + 5; 9 int dis[maxn];10 int d[maxn];11 12 #define inf 0x3f3f3f3f13 14 int main()15 {16 int t;17 cin>>t;18 while(t--) {19 int x,k,t;20 cin>>x>>k>>t;21 22 int l,r;23 24 l = r = 1;25 dis[1] = 0;26 d[1] = 1;27 28 for(int j=2;j<=x;j++) {29 30 dis[j] = inf;31 32 while(l<=r&&d[l]<j-t) l++;33 if(l<=r) dis[j] = dis[d[l]] + 1;34 if(j%k==0) dis[j] = min(dis[j],dis[j/k]+1);35 while(l<=r&&dis[d[r]]>=dis[j]) r--;36 d[++r] = j;37 38 }39 40 printf("%d\n",dis[x]);41 }42 43 return 0;44 }
BestCoder Round #89 1002 Fxx and game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。