[NOI2010]超级钢琴

Author Avatar
ZC 2月 03, 2019
  • 在其它设备中阅读本文章

今天写了个2048,那就写一下luoguP2048作下纪念吧

P2048 [NOI2010]超级钢琴

转自题解。

自己推的时候没想到怎样贪心出最优解。

转载

Description

有 $n$个音符,编号为 $1$ 至 $n$ 。第$i$个音符的美妙度为 $A_i$ 。

我们要找到$k$段超级和弦组成的乐曲,每段连续的音符的个数$x$满足$ L\leq x\leq R$,求乐曲美妙度的最大值。

Solution

贪心 + 堆 + RMQ

首先可以看到,每段超级和弦都是连续的,美妙度是这段区间内所有美妙度的和。可以想到,每次求解区间和显然是不合算的,所以考虑到用前缀和。

考虑暴力,我们需要把所有满足条件的字段抽出来排个序,但这实在是不可想象。所以考虑使用贪心思想来解决这个问题。

先想预处理。我们定义$MAX(o, l, r) = max{sum(t) - sum(o - 1) \ | \ l\leq t \leq r }$ ,即以$o$为左端点,右端点范围是 $[l, r]$的最大子段。求$sum()$就用前面说的前缀和。可以看出,$o$的位置是固定的。所以$sum(o - 1)$ 也是固定的。所以我们要求这个的最大值,只要$sum(t)$最大就可以了。即要求 $sum(t)$在 $[l, r]$中的最大值,那怎么快速地求出这个最大值呢?很显然,这不是 $RMQ$的活么。对$ RMQ$不熟悉的可以参考 。当然,具体计算的时候还要看看上界$r$是否超过了$n$ 。

接下来想怎么贪心。我们可以每次都选最优的子段,这样选$k$次显然就是我们所要的结果,那怎么找到最优解呢?用堆来将解存进去,每次堆顶的元素就是最优解。

考虑一个三元组$ (o, l, r) $表示以$o$为左端点,右端点的选择区间为$[l,r]$的 情况,我用了一个$struct$来表示这个三元组,但往往实际上每个情况需要额外记录这个情况的最优解$ t$,这个不麻烦,在 $struct$里面敲一个构造函数就可以了。

我们假设当前最大的三元组是 $(o, l, r)$ 。最优解位置是$t$ 。$ans$ 累加这个三元组的贡献。由于$t$已经被选中,对于这个 $o$, $t$已经不能重复选中,但最优解还可能存在于 tt 左右的两端区间中,所以提取出 $(o, l, r)$之后,为了避免重复且不丧失其他较优解,我们仍然要把 $(o, l, t - 1)$ , $(o, t + 1, r)$扔回堆里面去。显然地,在放回去之前应该保证区间的存在,即 $l = t$ 或$ r = t$的情况要进行特判。

最后实现的时候还要注意一点,$RMQ$ 原本数组里面记录的是最优解的值,但我们查询区间最大值的时候查询的是最优解的位置。所以数组里面存的是最优解的位置,要特殊处理。

#include<cstdio>
#include<queue>
#include<cmath>
namespace FastIO{struct Reader{char buf[1<<20],*s,*t;bool EOF_FLG;Reader():s(buf),t(buf),EOF_FLG(false) {};char gt() {return s==t&&((t=(s=buf)+fread(buf,1,1<<20,stdin))==s)?EOF:(*s++);}Reader& operator>>(char* str) {if(EOF_FLG)return *str=0,*this;while((*str=gt())!=' '&&*str!='\n'&&*str!=EOF)++str;if(*str==EOF)EOF_FLG=true;*str=0;return *this;}template<typename T>Reader&operator>>(T&x) {if(EOF_FLG)return *this;char c=0,d;while(c!=EOF&&(c<'0'||c>'9'))d=c,c=gt();if(c==EOF){EOF_FLG=true;return *this;}else x=0;while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=gt();if(d=='-')x=-x;return *this;}}in;struct Writer{char buf[1<<20],*s,*t;Writer():s(buf),t(buf+(1<<20)){}~Writer(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,1<<20,stdout),*s++=c):(*s++=c);}template<typename T>Writer&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[40],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}Writer&operator<<(const char*s) {while(*s)pt(*s++);return *this;}}out;}using namespace FastIO;
#define ll long long
#define Fur(i,x,y) for(int i=x;i<=y;i++)
int MIN(int x,int y){return x<=y?x:y;}
using namespace std;
#define N 500001
int n,k,L,R,mx[N][20];
ll s[N],ans=0;
struct rmq{
    int logn;
    void pre(){
        logn=log2(n);
        Fur(i,1,n)mx[i][0]=i;
        Fur(j,1,logn)
            Fur(i,1,n-(1<<j)+1){
                int x=mx[i][j-1],y=mx[i+(1<<(j-1))][j-1];
                mx[i][j]=(s[x]>s[y])?x:y;
            }
    }
    int ask(int l,int r){
        int k=log2(r-l+1),x=mx[l][k],y=mx[r-(1<<k)+1][k];
        return (s[x]>s[y])?x:y;
    }
}T;
struct node{
    int o,l,r,t;
    node(int o,int l,int r):o(o),l(l),r(r),t(T.ask(l,r)){}
};
bool operator < (node x,node y){return s[x.t]-s[x.o-1]<s[y.t]-s[y.o-1];}
priority_queue<node>q;
int main(){
    in>>n>>k>>L>>R;
    Fur(i,1,n)in>>s[i],s[i]+=s[i-1];
    T.pre();
    Fur(i,1,n)if(i+L-1<=n)q.push((node){i,i+L-1,MIN(i+R-1,n)});
    while(k--){
        node tmp=q.top();q.pop();
        int o=tmp.o,t=tmp.t,l=tmp.l,r=tmp.r;
        ans+=s[t]-s[o-1];
        if(l!=t)q.push((node){o,l,t-1});
        if(r!=t)q.push((node){o,t+1,r});
    }
    out<<ans<<"\n";
}