Codeforces 487b Strip, dp + RMQ（经典）

104 阅读 0 评论 69 点赞

我是靠谱客的博主殷勤斑马，这篇文章主要介绍Codeforces 487b Strip, dp + RMQ（经典），现在分享给大家，希望可以做个参考。

题意：有一个长度为n的数列，问是否能把这个数列切成连续的几段，使得 1.每一段长度大于等于l；2.每一段中的最大值和最小值之差小于等于s。如果能输出能切成的最小的段数，不能输出-1。
思路：非常经典的dp题目，假设dp[i]表示 $a_1...a_i$ 这个序列能切成的最小段数，如果不能dp[i] = INF。现在问题是

1.如何找到状态转移方程。考虑如果l = 3， s = 1，如果 $a_i = 5$ , $a_{i-1} = 3$ , 很明显 $a_1...a_i$ 无论如何都不能切成满足条件的小段，所以dp[i]=INF。再考虑如果对于 $a_i$ , $a_{j-k}...a_i$ , $a_j...a_i$ ,都是满足条件的一段，很容易想到dp[i] = min(dp[j-k]…dp[j]) + 1。 2. 有了状态转移方程，现在问题便是如何维护当前区间的最大值最小值以及与 $a_i$ 配对，满足条件的dp[j-k]…dp[j]的最小值，即RMQ问题。这里用ST表，线段树都可以，但是因为这里可以采用尺取法（二指针），区间是连续移动的（没有跳跃），所以还可以使用multiset 和单调队列来维护。因为这里n 只有 $10^5$ 所以使用multiset的复杂度是nlogn完全没有问题，使用单调队列的话是O(n),但是如果单调队列用标准库的deque实现的话，常数通常会比较大，对于数据量比较大的题目还是推荐自己手写。
代码：

/*************************************************************************
 *Multiset 版本
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 5;
const int INF = 0x3f3f3f3f;
int A[maxn];
int dp[maxn];

int main()
{
    int n, s, l;
    scanf("%d %d %d", &n, &s, &l);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
    }
    multiset<int> pre, cur;
    int i = 1, j = 1;
    for(i = 1; i <= n; i++) {
        cur.insert(A[i]);
        while(*cur.rbegin() - *cur.begin() > s) {
            cur.erase(cur.find(A[j]));
            if(pre.find(dp[j - 1]) != pre.end()) {
                pre.erase(pre.find(dp[j - 1]));
            }
            j++;
        }
        if(i - j + 1 >= l) pre.insert(dp[i - l]);
        if(pre.empty()) {
            dp[i] = INF;
        } else {
            dp[i] = *pre.begin() + 1;
        }
    }
    int ans = dp[n];
    if(ans >= INF) ans = -1;
    cout << ans << endl;
    return 0;
}

/*************************************************************************
 * 单调队列版本
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100000 + 5;
int A[maxn];
int dp[maxn];

deque<int> min_que, max_que, pre_que;
void add(int x) {
    while(!min_que.empty() && x < min_que.back()) min_que.pop_back();
    min_que.push_back(x);
    while(!max_que.empty() && x > max_que.back()) max_que.pop_back();
    max_que.push_back(x);
}

void del(int x) {
    if(!min_que.empty() && x == min_que.front()) min_que.pop_front();
    if(!max_que.empty() && x == max_que.front()) max_que.pop_front();
}

void pre_add(int x) {
    while(!pre_que.empty() && x < pre_que.back()) pre_que.pop_back();
    pre_que.push_back(x);
}
void pre_del(int x) {
    if(!pre_que.empty() && pre_que.front() == x) pre_que.pop_front();
}
int main()
{
    int n, s, l;
    scanf("%d %d %d", &n, &s, &l);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
    }

    int i = 1, j = 1;
    for(i = 1; i <= n; i++) {
        add(A[i]);
        while(max_que.front() - min_que.front() > s) {
            del(A[j]);
            pre_del(dp[j-1]);
            j++;
        }
        if(i - j + 1 >= l) pre_add(dp[i-l]);
        if(pre_que.empty()) dp[i] = INF;
        else dp[i] = pre_que.front() + 1;
    }
    int ans = dp[n];
    if(ans >= INF) ans = -1;
    cout << ans << endl;
    return 0;
}