【题解】Codeforces 354 D Transferring Pyramid

Problem

给定一个 $n$ 层的金字塔,一开始塔上每个位置都没有染色
你可以进行两种操作:

  1. 给某一个特定格子染色,代价为 $3$
  2. 给一个子金字塔(必须到最底层)染色,代价为 $2+​$ 大小

给定 $k​$ 个关键位置,问将这 $k​$ 个位置都染上颜色的最小代价

Thought

显然不可能对比较靠上的点进行 $2$ 操作
假设染色一个第 $i$ 层的点,总费用为 $(n-i+1)*(n-i+2)/2$
假设将所有点都单独染色,总费用为 $3k$

那么当 $3k\leq (n-i+1)*(n-i+2)/2​$ 时,就不可能对其进行 $2​$ 操作

算出能够进行 $2$ 操作的点必然是底下约 $\sqrt k$ 层的点

然后将金字塔整体变成一个下三角的形式

每次从右向左考虑,设 $f[i]$ 为当前处理从右往左数第 $i$ 列的情况
那么发现假设右侧还有需要选择的节点,必然是需要在当前(或者留到之后)用一个 $2$ 操作取覆盖的
对于所有的没有选择的节点,我们只需要用 $2$ 操作覆盖最“高”的那个即可
用 $f[i][j]$ 表示当前处理到第 $i$ 列,最高的没有处理的节点对应需要至少第 $j$ 行进行 $2$ 操作才能覆盖的最小花费

当 $j=0$ 时, $f[i][0]=min(f[i-1][k-1]+2+\frac{k*(k+1)}{2}+uper[i][k+1]*3)$

这意味着选择第 $i​$ 列第 $k​$ 行进行 $2​$ 操作,并且对上面的点进行 $1​$ 操作

当 $j\neq 0$ 时, $f[i][j]=min(f[i][j-1],f[i-1][j-1])+uper[i][j+1]*3)$

这意味着选择上面的点进行 $1$ 操作,不进行 $2$ 操作

为什么不进行 $2$ 操作呢?
显然如果留下了一个最高的没有处理节点高度为 $j$ 的点,任意的对比其低的节点进行操作都没有意义,因为最终都会在覆盖最高的节点时同时覆盖掉

并且覆盖最高节点的操作必然只会在第一种情况出现,否则如果上面的点不全部覆盖掉, $2$ 操作也就没有了意义

那么最终答案就是 $f[n][0]$ 啦!

发现空间可能开不下,所以使用滚动数组指针操作即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
struct Point {
    int x, y;
    bool operator < (const Point a) const {
        if(y == a.y) return x > a.x;
        return y > a.y;
    }
}p[N];
int n, m, num[N], now = 1;
int f[1010], g[1010];
int main() {
    n = read(); m = read();
    for(int i = 1; i <= m; ++ i) {
        p[i].x = read();
        p[i].y = read();
        ++ num[n - p[i].y + 1];
    }
    sort(p + 1, p + m + 1);
    memset(f, 0x3f3f3f3f, sizeof(f));
    memset(g, 0x3f3f3f3f, sizeof(g));
    g[0] = 0;
    int* F = f; int* G = g;
    for(int i = 1; i <= n; ++ i) {
        int sum = 0, prenow = now;
        F[0] = G[0] + num[i] * 3;
        for(int j = 1; j <= i && 4 + j * (j + 1) <= 6 * m; ++ j) {
            while(now <= m && p[now].y > n - i + 1) {++ now;}
            while(now <= m && p[now].y == n - i + 1 && p[now].x == n - j + 1) {++ sum; ++ now;}
            F[0] = min(F[0], G[j - 1] + 2 + j * (j + 1) / 2 + (num[i] - sum) * 3);
        }
        sum = 0; now = prenow;
        for(int j = 1; j <= i && 4 + j * (j + 1) <= 6 * m; ++ j) {
            while(now <= m && p[now].y > n - i + 1) {++ now;}
            while(now <= m && p[now].y == n - i + 1 && p[now].x == n - j + 1) {++ sum; ++ now;}
            F[j] = min(F[j - 1], G[j - 1] + (num[i] - sum) * 3);
        }
        swap(F, G);
    }
    printf("%d\n", G[0]);
    return 0;
}
Comments

添加新评论