Codeforces 1029B. Creating the Contest 动态规划O(nlogn)解法及单调队列O(n)解法

题目链接：http://codeforces.com/problemset/problem/1029/B

题目大意：从数组a中选出一些数组成数组b，要求 b[i+1]<=b[i]*2 。

一开始想到的是O(n^2)的动态规划，但是超时了，下面是超时的代码。

#include <iostream>

using namespace std;

const int maxn = 200020;

int n, a[maxn], f[maxn], res = 0;

int main() {

    cin >> n;

    for (int i = 0; i < n; i ++) cin >> a[i];

    for (int i = 0; i < n; i ++) {

        f[i] = 1;

        for (int j = i-1; j >= 0 && a[i] <= 2*a[j]; j --) {

            f[i] = max(f[i], f[j]+1);

        }

        if (f[i] > res) res = f[i];

    }

    cout << res << endl;

    return 0;

}

然后想到的是：

二分找最小的满足a[i]<=a[j]*2的那个j ，O(logn)的时间复杂度
线段树求区间[j,i-1]的最大值，O(logn)的时间复杂度

再加上外层的循环，时间复杂度会降到O(n * logn)。

代码：

#include <iostream>

using namespace std;

#define lson l, m, rt << 1

#define rson m+1, r, rt << 1 | 1

const int maxn = 200020;

int n, a[maxn], MAX[maxn<<2];

void pushUp(int rt) {

    MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);

}

void build(int l, int r, int rt) {

    if (l == r) {

        MAX[rt] = 0;

        return;

    }

    int m = (l+r) >> 1;

    build(lson);

    build(rson);

    pushUp(rt);

}

void update(int p, int val, int l, int r, int rt) {

    if (l == r) {

        MAX[rt] = val;

        return;

    }

    int m = (l + r) >> 1;

    if (p <= m) update(p, val, lson);

    else update(p, val, rson);

    pushUp(rt);

}

int query(int L, int R, int l, int r, int rt) {

    if (L <= l && r <= R) {

        return MAX[rt];

    }

    int m = (l + r) >> 1;

    int tmp = 0;

    if (L <= m) tmp = query(L, R, lson);

    if (R >= m+1) tmp = max(tmp, query(L, R, rson));

    return tmp;

}

int findL(int i) {

    return lower_bound(a, a+n+1, (a[i]+1)/2) - a;

}

int main() {

    cin >> n;

    build(1, n, 1);

    for (int i = 1; i <= n; i ++) cin >> a[i];

    for (int i = 1; i <= n; i ++) {

        int L = findL(i);

        int val;

        if (L >= i) val = 1;

        else {

            val = query(L, i-1, 1, n, 1) + 1;

        }

        update(i, val, 1, n, 1);

    }

    cout << query(1, n, 1, n, 1) << endl;

    return 0;

}

然后是O(n)的单调队列解法。

代码：

#include <iostream>

using namespace std;

const int maxn = 200020;

int n, a[maxn], MAX[maxn];

int st = 0, ed = 0, sum = 0;

int que[maxn];  // que存放id，id对应的最大长度是MAX[id]

void test() {

    cout << "[test]" << endl;

    for (int i = 1; i <= n; i ++) {

        cout << i << ": " << MAX[i] << endl;

    }

}

int main() {

    cin >> n;

    for (int i = 1; i <= n; i ++) cin >> a[i];

    int j = 1;

    for (int i = 1; i <= n; i ++) {

        while (j < i && !( a[i] <= 2 * a[j] )) {

            j ++;

        }

        while (st < ed && que[st] < j) st ++;

        if (st == ed) {

            MAX[i] = 1;

        } else {

            MAX[i] = MAX[ que[st] ] + 1;

        }

        sum = max(sum , MAX[i]);

        while (st < ed && MAX[ que[st] ] <= MAX[i]) {

            st ++;

        }

        que[ed++] = i;

    }

    // test();

    cout << sum << endl;

    return 0;

}

巴特西

Codeforces 1029B. Creating the Contest 动态规划O(nlogn)解法及单调队列O(n)解法

最新文章

热门文章

巴特西

Codeforces 1029B. Creating the Contest 动态规划O(nlogn)解法 及 单调队列O(n)解法

最新文章

热门文章

Codeforces 1029B. Creating the Contest 动态规划O(nlogn)解法及单调队列O(n)解法