[NOI2010] 超级钢琴 - 贪心,堆,ST表

这也算是第K大问题的套路题了（虽然我一开始还想了个假算法），大体想法就是先弄出最优的一批解，然后每次从中提出一个最优解并转移到一个次优解，用优先队列维护这个过程即可。

类似的问题很多，放在序列上的，放在图上的，改天可以考虑补个专题。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1000005;

int a[N],s[N],st[N][20],stp[N][20],n,k,L,R;

int query(int l,int r)

{

    int lg=log2(r-l+1);

    int tmp = max(st[l][lg],st[r-(1<<lg)+1][lg]);

    if(tmp==st[l][lg]) return stp[l][lg];

    else return stp[r-(1<<lg)+1][lg];

}

inline int eval(int o,int l,int r)

{

    return s[query(l,r)]-s[o-1];

}

struct Item

{

    int o,l,r;

    bool operator < (const Item &b) const

    {

        return eval(o,l,r) < eval(b.o,b.l,b.r);

    }

};

Item gen(int o,int l,int r)

{

    Item tmp;

    tmp.o=o;

    tmp.l=l;

    tmp.r=r;

    return tmp;

}

priority_queue <Item> q;

int ans = 0;

signed main()

{

    cin>>n>>k>>L>>R;

    for(int i=1;i<=n;i++)

    {

        cin>>a[i];

        s[i]=s[i-1]+a[i];

        st[i][0]=s[i];

        stp[i][0]=i;

    }

    for(int j=1;j<=19;j++)

        for(int i=1;i+(1<<j)-1<=n;i++)

        {

            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);

            if(st[i][j]==st[i][j-1])

                stp[i][j]=stp[i][j-1];

            else

                stp[i][j]=stp[i+(1<<(j-1))][j-1];

        }

    for(int i=1;i+L-1<=n;i++)

    {

        q.push(gen(i,i+L-1,min(i+R-1,n)));

    }

    while(k--)

    {

        Item p=q.top();

        q.pop();

        int tans = eval(p.o,p.l,p.r);

        ans += tans;

        int mid = query(p.l,p.r);

        if(mid!=p.l)

        {

            Item x=p;

            x.r=mid-1;

            if(x.r>=x.l) q.push(x);

        }

        if(mid!=p.r)

        {

            Item x=p;

            x.l=mid+1;

            if(x.r>=x.l) q.push(x);

        }

    }

    cout<<ans<<endl;

}

巴特西

[NOI2010] 超级钢琴 - 贪心,堆,ST表

最新文章

热门文章