This page looks best with JavaScript enabled

「POI2014」PTA-单调队列

 ·  ✏️ About  471 words  ·  ☕ 1 mins read · 👀... views

给定 $n$ 个点的高度,规定从 $1$ 点出发,跳到比高度小于当前点的点不消耗体力,否则消耗一点体力,最后到达 $n$ 点。

$q$ 次询问,每次询问有一个步伐限制 $k$ ,求最少耗费的体力。

链接

Luogu P3752

题解

很明显的一个dp。

状态转移方程:

$$
\begin{equation}
dp[i] = \min_{j \geq i-k}
\begin{cases}
dp[j] + 1 & ht[i] \geq ht[j]\
dp[j], & ht[i] < ht[j]
\end{cases}
\end{equation}
$$

注意到$j$随$i$的变化而单调递增,所以这个东西可以用单调队列来完成$O(n)$的复杂度。

不过有一点小问题,在于这个加一的问题。我们注意到,如果我们把dp的值当作第一关键字,高度当作第二关键字,如果最优解的高度较矮,加一之后也不会比次优解要差(单调队列里的最优和次优至少差$1$),所以我们可以如此优化。

时间复杂度$O(nq)$。

代码

 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
46
47
48
49
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1100000;
int n,m;
int num[MAXN], dp[MAXN];
deque<int> q;// 其中的int为pos

void init(){
    scanf("%d",&n);
    num[0] = 0x3f3f3f3f;
    for(int i = 1;i<=n;i++)
        scanf("%d",&num[i]);
}
bool cmp(int x,int y){
	// 1 -> x 的优先级大于y;0 -> y的优先级大于x
    if(dp[x]!=dp[y])
        return dp[x] < dp[y];
    return num[x] > num[y];
}
int getans(int k){
    dp[1] = 0;
    while(!q.empty()) q.pop_back();
    q.push_back(1);
    for(int i = 2;i<=n;i++){
        while(!q.empty() && q.front() < i-k)
            q.pop_front();
        dp[i] = dp[q.front()] + ((num[q.front()] > num[i])? 0: 1);
        while(!q.empty() && cmp(i,q.back()))
            q.pop_back();
        q.push_back(i);
    }
    return dp[n];
}

void solve(){
    scanf("%d",&m);
    int t;
    for(int i = 1;i<=m;i++){
        scanf("%d",&t);
        printf("%d\n",getans(t));
    }
}

int main(){
    init();
    solve();
    return 0;
}

cqqqwq
WRITTEN BY
cqqqwq
A student in Computer Science.

评论: