BestCoder Round #89 B題---Fxx and game（單調隊列），

BestCoder Round #89 B題---Fxx and game（單調隊列），

輸入描述

輸出描述

輸入樣例

輸出樣例

題意：中文題，不再贅述；

思路：  BC題解如下：

    從後往前推，可以得到狀態轉移方程dp[i]=(dp[k*i],dp[i+l])+1{1<=l<=t}   

    根據這個轉移方程我們需要快速求得min{dp[i+l]}(1<=l<=t)

    我們知道這種形式的就是單調隊列優化dp的標准形式

    維護一個dp[i]從隊頭到隊尾遞增的隊列 每次算好dp[i]的時候把隊尾中dp值大於等於dp[i]的都出隊 (出隊都是下標比i大的,值又沒i優,是無用的)

    然後dp[i]=min(dp[a[pre]],dp[k*i])+1

代碼如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
typedef long long LL;
int dp[1000005],a[1000005];
int pre,tail;

int main()
{
    int T,x,k,t;
    cin>>T;
    while(T--)
    {
        scanf("%d%d%d",&x,&k,&t);
        pre=0,tail=0;
        a[tail++]=x;
        dp[x]=0;
        for(int i=x-1;i>=1;i--)
        {
            dp[i] = (t!=0)?dp[a[pre]]+1:9999999;
            if((1LL*i*k)<=(LL)x) dp[i]=min(dp[i],dp[i*k]+1);
            if(a[pre]-t==i) pre++;
            while(dp[a[tail-1]]>=dp[i]&&tail>pre) tail--;
            a[tail++]=i;
        }
        printf("%d\n",dp[1]);
    }
    return 0;
}