luoguP2048 [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;

}

巴特西

luoguP2048 [NOI2010]超级钢琴

upd 2019.12.10 latex和markdown化

题意

最新文章

热门文章