Fxx and game，fxxandgame

Fxx and game，fxxandgame

可提交的傳送門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 }