首页 > 代码库 > HDU 5945 维护一个单调队列 dp

HDU 5945 维护一个单调队列 dp

2024-08-18 05:51:21   224人阅读

Fxx and game

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 688    Accepted Submission(s): 162


Problem Description
Young theoretical computer scientist Fxx designed a game for his students.

In each game, you will get three integers X,k,t.In each step, you can only do one of the following moves:

1.X=X−i(0<=i<=t).

2.if k|X,X=X/k.

Now Fxx wants you to tell him the minimum steps to make X become 1.
 

 

Input
In the first line, there is an integer T(1≤T≤20) indicating the number of test cases.

As for the following T lines, each line contains three integers X,k,t(0≤t≤106,1≤X,k≤106)

For each text case,we assure that it‘s possible to make X become 1。
 

 

Output
For each test case, output the answer.
 

 

Sample Input
2
9 2 1
11 3 3
 

 

Sample Output
4
3
 

 

Source
BestCoder Round #89
题意:给你三个数x，k，t 有两种操作 1.X=X−i(0<=i<=t) .2. if k|X,X=X/k . 问最少经过多少步使得x->1
题解:维护一个变换次数递增的单调队列
 1 /****************************** 2 code by drizzle 3 blog: www.cnblogs.com/hsd-/ 4 ^ ^    ^ ^ 5  O      O 6 ******************************/ 7 #include<bits/stdc++.h> 8 #include<map> 9 #include<set>10 #include<cmath>11 #include<queue>12 #include<bitset>13 #include<math.h>14 #include<vector>15 #include<string>16 #include<stdio.h>17 #include<cstring>18 #include<iostream>19 #include<algorithm>20 #pragma comment(linker, "/STACK:102400000,102400000")21 using namespace std;22 #define  A first23 #define B second24 const int mod=1000000007;25 const int MOD1=1000000007;26 const int MOD2=1000000009;27 const double EPS=0.00000001;28 typedef __int64 ll;29 const ll MOD=1000000007;30 const int INF=1000000010;31 const ll MAX=1ll<<55;32 const double eps=1e-8;33 const double inf=~0u>>1;34 const double pi=acos(-1.0);35 typedef double db;36 typedef unsigned int uint;37 typedef unsigned long long ull;38 int cas;39 int x,k,t,l,r;40 int d[1000006];41 int dis[1000006];42 int main()43 {44         scanf("%d",&cas);45         for(int i=1; i<=cas; i++)46         {47             scanf("%d %d %d",&x,&k,&t);48             l=r=1;49             d[1]=1;50             for(int j=2;j<=x;j++) dis[j]=INF;51             dis[1]=0;52             for(int j=2; j<=x; j++)53             {54                 while(l<=r&&d[l]<j-t) l++;//把队列中没有用的点去掉55                 if(l<=r) dis[j]=dis[d[l]]+1;56                 if(j%k==0) dis[j]=min(dis[j],dis[j/k]+1);57                 while(l<=r&&dis[d[r]]>=dis[j])r--;//将队列中变换次数多的去掉58                 d[++r]=j;59             }60             printf("%d\n",dis[x]);61         }62     return 0;63 }

 

HDU 5945 维护一个单调队列 dp


联系
我们