「AT1732」「CODE FESTIVAL 2015 OKINAWA OPEN」Jungle

AutumnKite

题解AtCoderCODE FESTIVAL 2015 OKINAWA OPEN

发布于：2019年3月9日

次浏览

题目传送门

题意

有 \(n\) 棵树，第 \(i\) 棵树高度为 \(a_i\)。你需要砍掉一些树，砍树规则如下：

只能砍最多 \(m\) 棵树。
对于每个 \(i\ (1\le i\le n-k+1)\)，满足 \([i,i+k-1]\) 中被砍掉的树的数量不超过 \(1\)。

被砍掉的树的位置的高度都变为 \(0\)。

求砍树后 \(\max\limits_{1\le i\le n-k+1}\sum\limits_{j=i}^{i+k-1} a_j\) 的最小值，即最小化所有长度为 \(k\) 的区间的树的高度之和的最大值。

\(n\le 10^5,a_i\le 10^9\)

一个错误但可以 AC 的贪心解法

求出 \(sum_i\) 表示以 \(i\) 结尾的长度为 \(k\) 的区间的 \(a_i\) 之和。然后求出 \(mx_i\) 表示所有包含 \(i\) 的长度为 \(k\) 的区间中，最大的 \(sum_j\) 减去 \(a_i\) 的值，即 \(mx_i=\max\limits_{i\le j< i+k}sum_j-a_i\)。

显然可以二分。二分答案 \(x\) 后，问题变成了一个判定性问题。

是否存在一种砍树的方法，使得所有长度为 \(k\) 的区间的树的高度之和都不超过 \(x\)。

可以发现，若一棵树 \(i\) 能砍，必须满足 \(mx_i\le x\)。对于每个不符合要求的区间，选择该区间中最后一棵能砍的树砍掉。可以发现，优先选最后一棵有时候是不优的，例如

1	[O X X O] X [O X X X]

这种情况（O 表示可以砍的树，X 表示不能砍的树，[...] 表示不符合条件的区间），显然方案是选两个区间的第一棵树。若优先选最后一棵，如果不考虑前后两个区间选择的树的距离，虽然也能得到“能”的答案，但方案是不满足要求的，可以用 [X X X O] X [O X X X] 的数据卡掉；如果考虑前后两个区间选择的树的距离，则会得到“不能”的答案，也是错误的。

我没有考虑前后两个区间选择的树的距离，所以 [X X X O] X [O X X X] 这种数据会得到一个偏小的答案，然而可以 AC。

附 hack 数据：

1 2	10 5 4 2 2 2 5 1 5 1 1 2 10

答案是 \(9\)，我的代码会输出 \(8\)。

贪心算法代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005
int n, m, k, a[N], h, t, Q[N];
long long sum[N], id[N];
void push(int x, long long *cp){ // 单调队列
    while (h <= t && cp[Q[t]] <= cp[x]) --t;
    Q[++t] = x;
}
bool check(long long x){
    h = 1, t = 1, Q[t] = k;
    for (register int i = 1; i <= n; i + k <= n ? push(i + k, sum) : void(0), ++i){
        if (Q[h] < i) ++h;
        if (sum[Q[h]] - a[i] <= x) id[i] = i; else id[i] = 0;
    }
    h = 1, t = 0;
    for (register int i = 1; i <= k; ++i) push(i, id);
    int s = 0;
    for (register int i = 1, p = 0; i <= n - k + 1; push(i + k, id), ++i){
        if (Q[h] < i) ++h;
        if (i <= p) continue;
        if (sum[i + k - 1] <= x) continue;
        p = int(id[Q[h]]), ++s;
        if (p == 0) return 0;
    }
    return s <= m;
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    for (register int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (register int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + a[i] - (i > k ? a[i - k] : 0); // 求 sum
    long long l = 0, r = 100000000000000ll, md, ans;
    while (l <= r) if (check(md = (l + r) >> 1)) ans = md, r = md - 1; else l = md + 1;
    printf("%lld\n", ans);
}

正确的解法

一个正确但效率较低的二分 +DP 解法

仍然求出 \(sum_i,mx_i\)，考虑二分。

考虑用 \(O(nk)\) 的时间进行一个 DP 来判断。

首先考虑这样一个 DP 状态：\(dp_i\) 表示前 \(i\) 棵树（不包括 \(i\)），满足所有长度为 \(k\) 的区间的和都不超过 \(x\)，且第 \(i-k\) 棵树必砍时，最少需要砍多少棵树。

考虑主动转移，枚举下一棵砍的树 \(i+j\ (j\ge 0)\)，若可以砍 \(i+j\)（即满足 \(mx_{i+j}\le x\) 且 \(\max\limits_{i\le p< i+j} sum_p\le x\)），则 \(dp_{i+j+k}\gets \min(dp_{i+j+k},dp_{i}+1)\)。

然而直接这样做是 \(O(n^2)\) 的。通过观察发现，若 \(j\ge k\)，则可以把 \(dp_i\) 先转移到 \(dp_{i+k}\)，再把 \(dp_{i+k}\) 向前转移。于是，我们只需要考虑 \(0\le j< k\) 即可。时间复杂度优化为 \(O(nk)\)。

总的时间复杂度为 \(O(nk\log ans)\)。

另一个正确但效率较低的 DP 解法

仍然求出 \(sum_i,mx_i\)，但不二分，直接进行 DP。

\(dp_{i,j}\) 表示前 \(j\) 棵树，砍了 \(i\) 棵，\(j\) 必须砍时 \(\max\limits_{k\le p< j+k}sum_p\) 的最小值。

当 \(i\) 确定时，记 \(Mx_j\) 表示前 \(j\) 棵树（不包括 \(j\)），砍了 \(i-1\) 棵树且最后一棵砍的树 \(t\) 满足 \(j-t\ge k\) 的 \(\max\limits_{k\le p< j} sum_p\) 的最小值。

其实求 \(Mx_j\) 的过程相当于一个 DP 的过程，显然有两种决策：当 \(t< j-k\) 时，\(Mx_j=\max(Mx_{j-1},sum_{j-1})\)；当 \(t=j-k\) 时，\(Mx_j=dp_{i-1,j-k}\)。所以有 \(Mx_j=\min(\max(Mx_{j-1},sum_{j-1}),dp_{i-1,j-k})\)。

求出 \(Mx_j\) 后，求 \(dp_{i,j}\) 就变得很显然：\(dp_{i,j}=\max(Mx_j,mx_j)\)，分别表示 \(\max\limits_{k\le p< j}sum_p\) 的最小值，以及 \(\max\limits_{j\le p< j+k}sum_p\) 的最小值，这两部分互不影响，所以可以独立计算。

求出 \(dp_{i,j}\) 后，求答案也变得很显然：由于 \(dp_{m,j}\) 并没有包括 \(\max\limits_{j+k\le p\le n}sum_p\)，把这部分与 \(dp_{m,j}\) 取 \(\max\) 即可。

可以使用滚动数组优化内存。时间复杂度为 \(O(nm)\)。

正解——两者之并

可以发现，\(m> \lceil \frac{n}{k}\rceil\) 与 \(m= \lceil \frac{n}{k}\rceil\) 的情况答案是相同的。所以 \(m\) 最大为 \(\lceil \frac{n}{k}\rceil\)。

上面的两个 DP，可以发现当 \(k\le 50\) 时第一个 DP 是可以过的。而 \(k>50\) 时，由于 \(m\) 的级别是 \(\frac{n}{k}\)，第二个 DP 可以过。

那么把两者合并一下就可以通过此题。

正解代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005
int n, m, k, a[N], h, t, Q[N];
long long sum[N], mx[N];
void push(int x){ // 单调队列维护
    while (h <= t && sum[Q[t]] <= sum[x]) --t;
    Q[++t] = x;
}
namespace Subtask1{ // 二分+DP O(nk log ans)
    int dp[N];
    void upd(int i, int j){
        if (i > n + 1) i = n + 1;
        dp[i] = std :: min(dp[i], j);
    }
    bool check(long long x){
        for (register int i = 1; i <= n + 1; ++i) dp[i] = 1e9;
        dp[1] = 0;
        for (register int i = 1; i <= n; ++i){
            long long Mx = 0;
            for (register int j = 0; j < k && i + j <= n; ++j){
                if (Mx <= x && mx[i + j] <= x) upd(i + j + k, dp[i] + 1);
                Mx = std :: max(Mx, sum[i + j]);
            }
            // if (x == 0) printf("%d %lld\n", i, Mx);
            if (Mx <= x) upd(i + k, dp[i]);
        }
        return dp[n + 1] <= m;
    }
    void Main(){
        long long l = 0, r = 1e14, md, ans;
        while (l <= r) if (check(md = (l + r) >> 1)) ans = md, r = md - 1; else l = md + 1;
        printf("%lld\n", ans);
    }
}
namespace Subtask2{ // DP O(nm)=O(n^2/k)
    long long dp[2][N];
    void Main(){
        long long Mx = 0;
        for (register int i = 1; i <= n; ++i){
            if (i > k) Mx = std :: max(Mx, sum[i - 1]);
            dp[1][i] = std :: max(Mx, mx[i]);
        }
        for (register int i = 2; i <= m; ++i){
            int t = i & 1;
            long long Mx = 0;
            for (register int j = 1; j <= n; ++j){
                if (j > k) Mx = std :: max(Mx, sum[j - 1]);
                if (j > k) Mx = std :: min(Mx, dp[!t][j - k]);
                dp[t][j] = std :: max(Mx, mx[j]);
            }
        }
        long long ans = 0x3f3f3f3f3f3f3f3fll;
        Mx = 0;
        for (register int i = n; i; --i){
            if (i + k <= n) Mx = std :: max(Mx, sum[i + k]);
            ans = std :: min(ans, std :: max(dp[m & 1][i], Mx));
        }
        printf("%lld\n", ans);
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    m = std :: min(m, n / k + 1);
    for (register int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (register int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + a[i] - (i > k ? a[i - k] : 0);
    h = 1, t = 1, Q[t] = k;
    for (register int i = 1; i <= n; i + k <= n ? push(i + k) : void(0), ++i){
        if (Q[h] < i) ++h;
        mx[i] = sum[Q[h]] - a[i];
    }
    if (m <= 2005) return Subtask2 :: Main(), 0;
    if (k <= 55) return Subtask1 :: Main(), 0;
}

更新于：2020年3月26日

二分

单调队列

RMQ

「Codeforces 1119F」Niyaz and Small Degrees

题目传送门题意给定一棵 \(n\) 个节点的树，有边权，对于所有 \(x\ (0\le x < n)\)，可以删去一些边，求使得所有节点的度数 \(\le x\) 的删掉的边的边权...

「AT1731」「CODE FESTIVAL 2015 OKINAWA OPEN」Implementation Addict

题目传送门题意有 \(n\) 天，每天有一个值 \(a_i\)（未确定的值），其中 \(a_i=0\) 的天数称为“休息”，其他的称为“工作”。若第 \(i\) 天为“工作”，设第 ...