首页 > > 程序设计 > C/C++ >

Fxx and game

2018-06-17 23:36:58来源：未知阅读 ()

可提交的传送门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 }