可提交的传送门http://acm.hdu.edu.cn/showproblem.php?pid=5945
分析：这道题目可以采用动态规划来解决
设f[i]表示把i变成1的最小代价。
所以有:f[i] = min{f[(1-t) ~ (i-1)]}+1
特别的,对于i % k == 0 f[i] = min{f[i],f[i/k] + 1}
我们可以先忽略掉特判的一步，这样，f[i]就来自于f[(1-t) ~ (i-1)]之间的最小值了
我们发现这个问题转换成了RMQ问题,可以在logn内解决
可以用单调队列优化dp，这样可以做到复杂度O(n)
1 #include <queue>
2 #include <cstdio>
3 #include <cstring>
4 #include <iostream>
5 #include <algorithm>
6 using namespace std;
7 typedef long long ll;
8 inline void read(int &x){
9 x=0;char ch;bool flag = false;
10 while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
11 while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
12 }
13 inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
14 inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
15 const int maxn = 1000010;
16 const int inf = 0x3f3f3f3f;
17 int f[maxn],q[maxn],l,r,ans;
18 inline void work(){
19 int n,k,t;
20 read(n);read(k);read(t);
21 if(t == 0){
22 for(ans=0;n>1;++ans) n /= k;
23 printf("%d\n",ans);
24 return;
25 }
26 l = r = 0;f[1] = 0;
27 q[0] = 1;
28 for(int i=2;i<=t+1 && i <= n;++i) f[i] = 1,q[++r] = i;
29 for(int i=t+2;i<=n;++i){
30 if(i % k == 0 && k != 1) f[i] = f[i/k] + 1;
31 else f[i] = inf;
32 while(l <= r && q[l] < (i - t)) ++l;
33 f[i] = cat_min(f[i],f[q[l]] + 1);
34 while(l <= r && f[q[r]] >= f[i]) --r;
35 q[++r] = i;
36 }
37 printf("%d\n",f[n]);
38 }
39 int main(){
40 int T;read(T);
41 while(T--) work();
42 getchar();getchar();
43 return 0;
44 }