HDOJ 5808 - Price List Strike Back

#动态规划 #整体二分 #背包动态规划

Published on 2016-08-07

描述

在 Byteland 一共有 $n(n\le 20000)$ 家商店，编号依次为 $1$ 到 $n$ 。每家商店只会卖一种物品，其中第 $i$ 家商店的物品单价为 $v_i(1\le v_i\le 100)$ ，且它到 Byteasar 的家的距离为 $d_i(d_i\le {10}^9)$ 。
Byteasar 每天都会进行一次购物，一共有 $m(m\le 100000)$ 天，第 $i$ 天他会选择一个区间 $[l_i, r_i]$ ，并给自己设定一个距离上限 $c_i(c_i\le {10^9})$ ，然后他会在编号在该区间内每家到自己家的距离不超过 $c_i$ 的商店购买最多一件物品，当然他也可以选择什么都不买。回家之后，Byteasar 会把今天购物所花的钱的总数 $\mathrm{sum}_i(\mathrm{sum}_i\le 100)$ 记录在账本上。
Byteasar 的数学不好，他可能会把花的钱记错。
请写一个程序，帮助 Byteasar 判断每条记录是否一定是错的。
注意：记多或者记少都算记错。

分析

采用整体二分，利用函数 solve(Q, l, r) 来解决队列 $Q$ 内的询问，其中保证 $Q$ 中的询问区间 $[l_i, r_i)$ 满足 $l\le l_i\le r_i < r$ 。

令 $\mathrm{mid} = \frac {l + r} 2$ ，则完全在 $\mathrm{mid}$ 左边的询问以及完全在 $\mathrm{mid}$ 右边的询问都可以递归解决，唯一需要解决的穿过 $\mathrm{mid}$ 的询问。

设 $f_{i, j}$ 为在 $[i, mid)$ 商店区间买 $j$ 的物品，最大距离的最小值； $g_{i, j}$ 为在 $[mid, i)$ 商店区间买 $j$ 的物品，最大距离的最小值。这个就是一个简单的背包问题，可以在 $O(Vn)$ 的时间内求出（ $V$ 是 $\mathrm{sum}$ 的最大值）。
则穿过 $\mathrm{mid}$ 的询问的答案为 $c_i < \min\max_{0\le j\le \mathrm{sum}_i}(f_{l_i, j}, g_{r_i, \mathrm{sum}_i - j})$ 。
复杂度为 $T(n) = 2T(\frac n 2) + Vn$ ，根据主定理解出复杂度为 $O(Vn\log n)$ 。

~~瞎扯：~~
这可能不叫整体二分，因为我们并没有二分一个答案，但这也不是 CDQ 分治，因为前面的询问对后面的询问不构成任何影响。这应该是对询问序列的分治，但因为有一个将询问按照查询的区间归类的步骤，我还是叫它整体二分。
如果所有的询问都包含同一个点，那么我们可以直接以这个点为中心向前向后各做一次背包，但是如果没有交点的话，就不能一次处理所有询问了，所以采取将商店序列二分的方法，来保证能够在合理的时间内，实现这个结构。

代码

//  Created by Sengxian on 8/7/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  HDOJ 5808 整体二分
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}
typedef long long ll;

const int maxn = 20000 + 3, maxm = 100000 + 3, maxv = 100 + 3, INF = 0x3f3f3f3f;
struct query {
    int l, r, c, sum;
}qs[maxm];

int n, m, v[maxn], d[maxn], q[maxm], q1[maxm], q2[maxm], tmp[maxm];
int f[maxn][maxv], g[maxn][maxv], ans[maxm];

void solve(int ql, int qr, int l, int r) {
    if (l >= r || ql >= qr) return;
    if (r - l == 1) {
        for (int i = ql; i < qr; ++i)
            ans[q[i]] = !(qs[q[i]].sum == v[l] && qs[q[i]].c >= d[l]);
        return;
    }
    int mid = (l + r) / 2, cnt1 = 0, cnt2 = 0, cnt = 0;
    for (int i = ql; i < qr; ++i) {
        if (qs[q[i]].r <= mid) q1[cnt1++] = q[i];
        else if (qs[q[i]].l >= mid) q2[cnt2++] = q[i];
        else tmp[cnt++] = q[i];
    }
    for (int i = 0; i < cnt1; ++i) q[ql + i] = q1[i];
    for (int i = 0; i < cnt2; ++i) q[ql + cnt1 + i] = q2[i];

    //f[i][j] [i, mid) 商店买 j 的物品，最大距离的最小值    
    //g[i][j] [mid, i) 商店买 j 的物品，最大距离的最小值    
    memset(f[mid], INF, sizeof f[mid]);
    f[mid][0] = 0;
    for (int i = mid - 1; i >= l; --i)
        for (int j = 0; j < maxv; ++j) {
            f[i][j] = f[i + 1][j];
            if (j >= v[i]) f[i][j] = min(f[i][j], max(f[i + 1][j - v[i]], d[i]));
        }
    memset(g[mid], INF, sizeof g[mid]);
    g[mid][0] = 0;
    for (int i = mid; i < r; ++i)
        for (int j = 0; j < maxv; ++j) {
            g[i + 1][j] = g[i][j];
            if (j >= v[i]) g[i + 1][j] = min(g[i + 1][j], max(g[i][j - v[i]], d[i]));
        }
    for (int i = 0; i < cnt; ++i) {
        int res = INT_MAX;
        for (int j = 0; j <= qs[tmp[i]].sum; ++j)
            res = min(res, max(f[qs[tmp[i]].l][j], g[qs[tmp[i]].r][qs[tmp[i]].sum - j]));
        ans[tmp[i]] = res > qs[tmp[i]].c;
    }

    solve(ql, ql + cnt1, l, mid);
    solve(ql + cnt1, ql + cnt1 + cnt2, mid, r);
}

int main() {
    int caseNum = ReadInt();
    while (caseNum--) {
        n = ReadInt(), m = ReadInt();
        for (int i = 0; i < n; ++i) v[i] = ReadInt();
        for (int i = 0; i < n; ++i) d[i] = ReadInt();
        for (int i = 0; i < m; ++i) {
            qs[i].l = ReadInt() - 1, qs[i].r = ReadInt();
            qs[i].c = ReadInt(), qs[i].sum = ReadInt();
            q[i] = i;
        }
        solve(0, m, 0, n);
        for (int i = 0; i < m; ++i) putchar('0' + ans[i]);
        putchar('\n');
    }
    return 0;
}

BZOJ 1977 - [BeiJing2010组队]次小生成树 Tree Codeforces 703D - Mishka and Interesting sum

Sengxian's Blog

HDOJ 5808 - Price List Strike Back

描述

分析

代码