SP350 LANDSCAP - Landscaping 题解

· · 题解

我们先看一下题目样例，有这么一个部分：

    * * *     *
  * * * * *   * * *   *
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2

再看一下它给的删除方法：

    * * *     -
  * * * * *   - - -   -
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2

像不像拿着一根线从高往低扫掉最小的“山峰”？也就是说只要能够在知道该“山峰”峰顶时就知道它的大小，那么就贪心的把当前这个线扫到的最小“山峰”削掉就行。

But，有可能是我菜了，我不知道怎么在知道该“山峰”峰顶时就知道它的大小。所以这个复杂度有可能接近与 K 同阶的算法就交给读者了（虽然我也不知道它的正确性如何证明或证伪，但是读者自证不难）

我们把图倒过来看一下：

1 2 3 3 3 2 1 3 2 2 1 2
* * * * * * * * * * * *
  * * * * *   * * *   *
    * * *     *

是不是很像一棵树？第 0 行为根节点，向下是区间状的子节点（有点线段树的感觉）

所以问题就从把 n - k 座山峰削平的最少花费转化成了保留 k 个子树的最大权值。

显然子树的权值就是子树的大小，所以问题很明显为一个树形DP，转移方程为： 设 dp_{u, i} 表示以 u 为根，剩余叶子数量不大于于 i 的最大权值和， sum 为整棵树的权值和，则有：

dp_{u, i} = \max_{j}^{i - 1} dp_{v, j} + dp_{u, i - j} \\ result = sum - f_{1, k}

但是怎么建树呢。

注意到一个平面 S 的父节点平面 F 应当有：

F_l \leq S_l \leq S_r \leq F_r

所以用两次单调栈即可求出一个区间的父区间。

时间复杂度：

O(nk^2)

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, K = 30;
int n, k, h[N], pt[N], ct, idx[N], stk[N], top;
int head[N], cnt, pre[N], nxt[N];
int sz[N], f[N][K], sum;
struct edge {
    int to, nxt;
} e[N];
void dfs(int u) {
    sum += sz[u];
    for(int i = 0; i <= k; i ++) f[u][i] = sz[u];
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        dfs(v);
        for(int j = k; j >= 1; j --) {
            for(int k = j - 1; k >= 0; k --) {
                f[u][j] = max(f[u][j], f[v][j - k] + f[u][k]);   
            }
        }
    }
}
bool cmp(int a, int b) {
    return h[a] < h[b] || (h[a] == h[b] && a < b);
}
int main() {
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i ++) scanf("%d", &h[i]);
    for(int i = 1; i <= n; i ++) idx[i] = i;
    sort(idx + 1, idx + n + 1, cmp);
    top = 1;
    stk[top] = 0;
    for(int i = 1; i <= n; i ++) {
        while(top >= 1 && h[stk[top]] > h[i]) -- top;
        pre[i] = stk[top], stk[++ top] = i;
    }
    top = 1;
    stk[top] = n + 1;
    for(int i = n; i >= 1; i --) {
        while(top >= 1 && h[stk[top]] >= h[i]) -- top;
        nxt[i] = stk[top], stk[++ top] = i;
    }
    for(int j = 1; j <= n; j ++) {
        int i = idx[j];
        int u = nxt[i];
        if(h[pre[i]] >= h[nxt[i]]) u = pre[i];
        if(h[pre[i]] == h[i]) {
            pt[i] = pt[pre[i]];
            continue;
        }
        ct ++;
        pt[i] = ct;
        sz[pt[i]] = (nxt[i] - pre[i] - 1) * (h[i] - h[u]);

        e[++ cnt].to = ct;
        e[cnt].nxt = head[pt[u]];
        head[pt[u]] = cnt;
    }
    dfs(1);
    printf("%d", sum - f[1][k]);
    return 0;
}