P2048 [NOI2010]超级钢琴

upd 2019.12.10 latex和markdown化

题意

解析：

先考虑暴力:将每个区间求出来,放进一个堆里,取出前k个就是答案。

期望得分：20,原因:TLE

code(对,我真写了):

#include<bits/stdc++.h>
using namespace std;
const int maxn=5*1e5+10;
int n,k,L,R,ans;
int sum[maxn];
priority_queue<int> q;
int main()
{
    scanf("%d%d%d%d",&n,&k,&L,&R);
    for(int i=1;i<=n;i++) scanf("%d",&sum[i]),sum[i]+=sum[i-1];
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            if(j-i+1>=L&&j-i+1<=R) q.push(sum[j]-sum[i-1]);
    for(int i=1;i<=k;i++) ans+=q.top(),q.pop();
    printf("%d",ans);
    return 0;
}

考虑优化,先看这道题

这道题中我们并没有将所有的组合全部求出,而是先将一些最优解放入堆中,取出后放入次于它的最优解来更新。

这道题也可以用相同的方法来优化。

首先区间和肯定用前缀和优化了。

我们先固定左端点,将从每个点向右的最优解放入,记为四元组:\((x,l,r,t)\),\(x\)是左端点,\(l\)和\(r\)是右端点的范围,t是当前解的右端点的位置。求解该区间的最优解可以用ST表解决。

将这些数放入后,我们每从堆中取出一个四元组\((x,l,r,t)\),加上它的答案后,向堆中放入\((x,l,t-1,query(l,t-1))\)和\((x,t+1,query(t+1,r))\)(相当于放入对于\(x\)的\([l,r]\)区间除去\(t\)后的最优解,注意判断\(l,r\)是否为\(t\))

取\(k\)次即为答案。

之前做过的题思想还是要记住的~

code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5*1e5+10;
int n,k,L,R;
int st[maxn][30];
ll ans;
ll sum[maxn];
void init()
{
    for(int i=1;i<=n;i++) st[i][0]=i;
    int t=(int)log2(n);
    for(int j=1;j<=t;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            int x=st[i][j-1],y=st[i+(1<<(j-1))][j-1];
            st[i][j]=sum[x]>sum[y]?x:y;
        }
}
int query(int l,int r)
{
    int k=(int)log2(r-l+1);
    int x=st[l][k],y=st[r-(1<<k)+1][k];
    return sum[x]>sum[y]?x:y;
}
struct node
{
    int x,l,r,t;
    bool operator < (const node& y)const
    {
        return sum[t]-sum[x-1]<sum[y.t]-sum[y.x-1];
    }
};
priority_queue<node> q;
int main()
{
    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];
    init();
    //puts("1111");
    for(int i=1;i<=n;i++)
        if(i+L-1<=n) q.push((node){i,i+L-1,min(n,i+R-1),query(i+L-1,min(n,i+R-1))});//puts("111");
    //puts("11");
    while(k--)
    {
        int x=q.top().x,l=q.top().l,r=q.top().r,t=q.top().t;
    //  printf("%d %d %d %d\n",x,l,r,t);
        q.pop();ans+=sum[t]-sum[x-1];
        //puts("111");
        if(l!=t) q.push((node){x,l,t-1,query(l,t-1)});
        if(r!=t) q.push((node){x,t+1,r,query(t+1,r)});
        //puts("111");
    }
    printf("%lld",ans);
    return 0;
}