可提交的传送门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)
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=*x+ch-'',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = ;
const int inf = 0x3f3f3f3f;
int f[maxn],q[maxn],l,r,ans;
inline void work(){
int n,k,t;
read(n);read(k);read(t);
if(t == ){
for(ans=;n>;++ans) n /= k;
printf("%d\n",ans);
return;
}
l = r = ;f[] = ;
q[] = ;
for(int i=;i<=t+ && i <= n;++i) f[i] = ,q[++r] = i;
for(int i=t+;i<=n;++i){
if(i % k == && k != ) f[i] = f[i/k] + ;
else f[i] = inf;
while(l <= r && q[l] < (i - t)) ++l;
f[i] = cat_min(f[i],f[q[l]] + );
while(l <= r && f[q[r]] >= f[i]) --r;
q[++r] = i;
}
printf("%d\n",f[n]);
}
int main(){
int T;read(T);
while(T--) work();
getchar();getchar();
return ;
}