hdu 5945 Fxx and game(单调队列优化DP)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：hdu 5945 Fxx and game

题意：

让你从x走到1的位置，问你最小的步数，给你两种走的方式，1.如果k整除x，那么你可以从x走一步到k。2.你可以从x走到j，j+t<=x

题解：

看这个数据规模，多半要用O(N)的做法，比赛的时候我当时用的贪心，但这肯定是错的，最终FST了，当时不会单调队列。

我们设dp[i]，表示走到i的最小步数，那么就有dp[i]=min{dp[i/k]（k|i），dp[j]+1(j+t<=x)}。

对于第一项，我们直接判断一下就行了，对于第二项，我们可以用单调队列来优化。

 #include<bits/stdc++.h>

 #define F(i,a,b) for(int i=a;i<=b;++i)

 using namespace std;

 const int N=1e6+;

 int x,k,_,t,dp[N],Q[N];

 int main()

 {

     scanf("%d",&_);

     while(_--)

     {

         scanf("%d%d%d",&x,&k,&t);

         int head=,tail=;

         dp[]=,Q[++tail]=;

         F(i,,x)

         {

             while(head<tail&&Q[head]+t<i)head++;

             dp[i]=dp[Q[head]]+;

             if(i%k==)dp[i]=min(dp[i],dp[i/k]+);

             while(head<tail&&dp[Q[tail]]>dp[i])tail--;

             Q[++tail]=i;

         }

         printf("%d\n",dp[x]);

     }

     return ;

 }