P2048 [NOI2010]超级钢琴

桃扇骨 2023-08-17 15:46 165阅读 0赞

## 题目描述 ##

小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。

这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。

一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。

小Z决定创作一首由k个超级和弦组成的乐曲，为了使得乐曲更加动听，小Z要求该乐曲由k个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。

## 输入格式 ##

输入第一行包含四个正整数n, k, L, R。其中n为音符的个数，k为乐曲所包含的超级和弦个数，L和R分别是超级和弦所包含音符个数的下限和上限。

接下来n行，每行包含一个整数Ai，表示按编号从小到大每个音符的美妙度。

## 输出格式 ##

输出只有一个整数，表示乐曲美妙度的最大值。

## 输入输出样例 ##

**输入 \#1**复制

4 3 2 3
    3
    2
    -6
    8

**输出 \#1**复制

#include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<queue>
    #define MAXN 500005
    #define LOG 20
    #define max(x, y) ((x) > (y) ? (x) : (y))
    #define min(x, y) ((x) < (y) ? (x) : (y))
    long long sum[MAXN], table[MAXN][LOG];
    namespace RMQ {
        void init(int n) {
            for (int i = 1; i <= n; i++) table[i][0] = i;
            for (int j = 1; (1 << j) <= n; j++)
                for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                    int x = table[i][j - 1], y = table[i + (1 << (j - 1))][j - 1];//注意这里的优先级
                    table[i][j] = sum[x] > sum[y] ? x : y;
                }
        }
        int query(int l, int r) {
            int k = log2(r - l + 1);
            int x = table[l][k], y = table[r - (1 << k) + 1][k];
            return sum[x] > sum[y] ? x : y;
        }
    }
    struct element {
        int o, l, r, t;
        element() {}
        element(int o, int l, int r) : o(o), l(l), r(r), t(RMQ::query(l, r)) {}
        friend bool operator < (const element& a, const element& b) {
            return sum[a.t] - sum[a.o - 1] < sum[b.t] - sum[b.o - 1];
        }
    };
    std::priority_queue< element > Q;
    int main() {
        int n, k, L, R;
        scanf("%d%d%d%d", &n, &k, &L, &R);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &sum[i]);
            sum[i] += sum[i - 1];
        }
        RMQ::init(n);
        for (int i = 1; i <= n; i++)
            if (i + L - 1 <= n) 
                Q.push(element(i, i + L - 1, min(i + R - 1, n)));
        long long ans = 0;
        while (k--) {
            int o = Q.top().o, l = Q.top().l, r = Q.top().r, t = Q.top().t;
            Q.pop();
            ans += sum[t] - sum[o - 1];
            if (l != t) Q.push(element(o, l, t - 1)); 
            if (t != r) Q.push(element(o, t + 1, r));
        }
        printf("%lld\n", ans);
        return 0;
    }