Fxx and game

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

Problem Description

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

In each game, you will get three integers

Input

In the first line, there is an integer

Output

For each test case, output the answer.

Sample Input

2 9 2 1 11 3 3

Sample Output

4 3

分析：dp+单调队列（需手写，否则难以卡过去）；

代码：

手写：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set
                      
                       ::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector
                       
                        #define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair
                        
                         #define Lson L, mid, ls[rt]#define Rson mid+1, R, rs[rt]#define sys system("pause")#define freopen freopen("in.txt","r",stdin)const int maxn=1e6+10;using namespace std;ll gcd(ll p,ll q){ return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){ if(q&1)f=f*p;p=p*p;q>>=1;}return f;}inline ll read(){ ll x=0;int f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int n,m,k,t,d[maxn],f[maxn],head,tail;int main(){ int i,j; scanf("%d",&t); while(t--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); memset(d,inf,sizeof(d)); d[a]=0; head=tail=a; f[head]=a; for(i=a-1;i>=1;i--) { if((ll)i*b<=a)d[i]=d[i*b]+1; while(head<=tail&&f[tail]-i>c)tail--; if(head<=tail)d[i]=min(d[i],d[f[tail]]+1); f[--head]=i; while(head
                         
                          d[f[head]])f[head+1]=f[head],head++; } printf("%d\n",d[1]); } //system("Pause"); return 0;}

stl：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set
                      
                       ::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector
                       
                        #define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair
                        
                         #define Lson L, mid, ls[rt]#define Rson mid+1, R, rs[rt]#define sys system("pause")#define freopen freopen("in.txt","r",stdin)const int maxn=1e6+10;using namespace std;ll gcd(ll p,ll q){ return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){ if(q&1)f=f*p;p=p*p;q>>=1;}return f;}inline ll read(){ ll x=0;int f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int n,m,k,t,dp[maxn];struct node{ int c,id; node(int _c,int _id):c(_c),id(_id){} bool operator<(const node&p)const { return c>p.c; }};priority_queue
                         
                          pq;int main(){ int i,j; scanf("%d",&t); while(t--) { int a,b,c; while(!pq.empty())pq.pop(); scanf("%d%d%d",&a,&b,&c); memset(dp,inf,sizeof(dp)); pq.push(node(0,a)); dp[a]=0; for(i=a-1;i>=1;i--) { while(!pq.empty()) { node x=pq.top(); if(x.id-i>c)pq.pop(); else { dp[i]=x.c+1; break; } } if((ll)b*i<=a)dp[i]=min(dp[i],dp[i*b]+1); pq.push(node(dp[i],i)); } printf("%d\n",dp[1]); } //system("Pause"); return 0;}