[原创]HDU 5945 Fxx and game [单调队列+dp]【动态规划】

2016-10-30 21:38:33 Tabris_ 阅读数：270

博客爬取于2020-06-14 22:42:56
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52974565

题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=5945
------------------------------------.

问题描述
青年理论计算机科学家Fxx给的学生设计了一款数字游戏。

一开始你将会得到一个数:XX，每次游戏将给定两个参数:k,tk,t, 任意时刻你可以对你的数执行下面两个步骤之一：

1.:X = X - i(1 <= i <= t)1.X=X−i(1<=i<=t)。

2.:2.若:X:X为:k:k的倍数，X = X / kX=X/k。

现在Fxx想要你告诉他最少的运行步骤，使:X:X变成:11。
输入描述
第一行一个整数:T(1\leq T\leq20):T(1≤T≤20)表示数据组数。

接下来:T:T行，每行三个数:X,k,t(0\leq t\leq10^6,1\leq X,k\leq10^6)X,k,t(0≤t≤10^ 6 ,1≤X,k≤10^ 6 )

数据保证有解。
输出描述
输出共:T:T行。

每行一个整数表示答案。
输入样例
2
9 2 1
11 3 3
输出样例
4
3

---------------------------------------.

题目大意:中文题 不解释.

解题思路:

很容易先到是一个sbDP
状态转移方程就是
if(0==i%k)dp[i]=min(dp[i],dp[i/k]+1);
dp[i]=min(dp[i],min{dp[i+1],dp[i+2],,dp[i+t]}+1);
上述转移方程很好设计 但是因为数据很大 所以min{dp[i+1],dp[i+2],,dp[i+t]}这个操作如果暴力求解的话复杂度是O(xt) 很不现实 ，所以要优化 。

首先想到的是挂到线段树上 每次更新一个点+查询一个区间最小值 这样的话复杂度就降到O(x*logt) 然后发现还是会超时 ，于是乎就GG了

最后结束之后发现这是一个叫做单调队列优化的东西 于是借鉴巨巨们的博客http://blog.csdn.net/guhaiteng/article/details/52972757

学习到了
单调队列 其实就是一个通过维护下标在O(1)内知道区间最小值的东西
其实有点模拟数组的思想

然后根据题意
确定一下值的范围 ，删去无用值 ，每次操作都是线性的。
这样下来 总的时间复杂度就是O(n)

好高端的东西 现在理解的还不是那么特别透 。。。。继续努力。

然后

附本题代码
------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# include <bits/stdc++.h>
using namespace std;

# define INF 0x3f3f3f3f
# define pb push_back
# define abs(a) (a)>0?(a):-(a)
# define lalal puts("*******")
typedef long long int LL ;
typedef unsigned long long int LLu ;
/*******************************/

const int MOD = 1e9+7;
const int N = 1000005;
const double eps = 1e-9;


int dp[N],deq[N];//单调队列 维护下标

int main()
{
    int _;
    while(~scanf("%d",&_)){
        while(_--){

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

            int l,r;
            l=r=1;
            deq[1]=1,dp[1]=0;

            for(int i=2;i<=x;i++){
                dp[i]=10101010;
                while(l<=r&&deq[l]<i-t)l++; //确定范围的左值 在t的范围内
                if(l<=r)dp[i]=dp[deq[l]]+1;
                if(0==i%k)dp[i]=min(dp[i],dp[i/k]+1);
                while(l<=r&&dp[deq[r]] >= dp[i]) r--;  //维护右值 使无用的数据删除掉
                deq[++r] = i; //入队
            }

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