NOI2010...BZOJ2006 超级钢琴贪心

本文主要是介绍NOI2010...BZOJ2006 超级钢琴贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。小Z决定创作一首由k个超级和弦组成的乐曲，为了使得乐曲更加动听，小Z要求该乐曲由k个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。

Input

第一行包含四个正整数n, k, L, R。其中n为音符的个数，k为乐曲所包含的超级和弦个数，L和R分别是超级和弦所包含音符个数的下限和上限。接下来n行，每行包含一个整数Ai，表示按编号从小到大每个音符的美妙度。

Output

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

这道题直接贪心处理~~~

可以枚举全部符合的条件的超级和弦并将其值放入优先队列，然后直接贪心取出前K个~~

但是这样子的话可能会有很多种情况~

在这里，加入了许多一直用不到的和弦。

如果枚举的超级和弦按照开头下标进行归类的话，每次最多选择其中一类的某一个和弦。

所以这里可以用一个集合的形式代表某一类，并找出该类的最大值放入到优先队列。

每次取出其中一类的某一个和弦之后，该类又可以分为两个新类放入到优先队列

直到取出K个为止

这样子就可以有效的减少枚举情况了~~~

so....
维护一个优先队列，里面放着一个四元数据（i,l,r,t）

四元数据（i,l,r,t）：=左端点为i,右端点在[l,r]中这么多个选择的最大值的下标为t~~~

i、l、r直接暴力就可以得出~~主要是t~~
要使sum[l,t]的值最大~~转换成求sum[1,t](t属于[l,r])最大

所以这里维护一个前缀和sum,然后求出区间[l,r]最大值的下标即可~~RMQ~~

每次取出队列顶点之后,如果[l,t-1]、[t+1,r]可以形成正确的数据，还要添加到队列里~~

#include <algorithm>
#include <iostream>
#include<string.h>
#include <fstream>
#include <math.h>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define exp 1e-8
#define fi first
#define se second
#define ll long long
#define INF 0x3f3f3f3f
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define mm(a,b) memset(a,b,sizeof(a));
#define for0(a,b) for(int a=0;a<=b;a++)//0---(b-1)
#define for1(a,b) for(int a=1;a<=b;a++)//1---(b)
#define rep(a,b,c) for(int a=b;a<=c;a++)//b---c
#define repp(a,b,c)for(int a=b;a>=c;a--)///
#define cnt_one(i) __builtin_popcount(i)
#define stl(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
using namespace std;
void bug(string m="here"){cout<<m<<endl;}
template<typename __ll> inline void READ(__ll &m){__ll x=0,f=1;char ch=getchar();while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}m=x*f;}
template<typename __ll>inline void read(__ll &m){READ(m);}
template<typename __ll>inline void read(__ll &m,__ll &a){READ(m);READ(a);}
template<typename __ll>inline void read(__ll &m,__ll &a,__ll &b){READ(m);READ(a);READ(b);}
template<typename __ll>inline void read(__ll &m,__ll &a,__ll &b,__ll &c){READ(m);READ(a);READ(b);READ(c);}
template<typename __ll>inline void read(__ll &m,__ll &a,__ll &b,__ll &c,__ll &d){READ(m);READ(a);READ(b);READ(c);read(d);}
template < class T > inline  void out(T a){if(a>9)out(a/10);putchar(a%10+'0');}
template < class T > inline  void outln(T a){if(a>9)out(a/10);putchar(a%10+'0');puts("");}
template < class T > inline  void out(T a,T b){out(a);putchar(' ');out(b);}
template < class T > inline  void outln(T a,T b){out(a);putchar(' ');outln(b);}
template < class T > inline  void out(T a,T b,T c){out(a);putchar(' ');out(b);putchar(' ');out(c);}
template < class T > inline  void outln(T a,T b,T c){out(a);putchar(' ');outln(b);putchar(' ');outln(b);}
template < class T > T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template < class T > T lcm(T a, T b) { return a / gcd(a, b) * b; }
template < class T > inline void rmin(T &a, const T &b) { if(a > b) a = b; }
template < class T > inline void rmax(T &a, const T &b) { if(a < b) a = b; }
template < class T > T pow(T a, T b) { T r = 1; while(b > 0) { if(b & 1) r = r * a; a = a * a; b /= 2; } return r; }
template < class T > T pow(T a, T b, T mod) { T r = 1; while(b > 0) { if(b & 1) r = r * a % mod; a = a * a % mod; b /= 2; } return r; }const int maxn=500005;
int sum[maxn];
int n,k,L,R;
ll ans;
struct DAT
{int i,l,r,t;DAT(){}DAT(int _i,int _l,int _r,int _t){i=_i,l=_l,r=_r,t=_t;}bool operator < (const DAT &rhs)const{return sum[t]-sum[i-1]<sum[rhs.t]-sum[rhs.i-1];}
};
priority_queue<DAT>que;
int f[maxn][20];
void rmq_init()
{for(int i=1;i<=n;i++)f[i][0]=i;for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++){int x=f[i][j-1],y=f[i+(1<<(j-1))][j-1];f[i][j]=sum[x]>sum[y]?x:y;}
}
int rmq(int l,int r)
{int k=0;while((1<<(k+1))<=r-l+1)k++;int x=f[l][k],y=f[r-(1<<k)+1][k];return sum[x]>sum[y]?x:y;
}
void solve()
{ans=0;for1(i,n)if(i+L-1<=n){int t=min(n,i+R-1);que.push(DAT(i,i+L-1,t,rmq(i+L-1,t)));}while(k--){DAT cur=que.top();que.pop();ans+=sum[cur.t]-sum[cur.i-1];if(cur.t-1>=cur.l)que.push(DAT(cur.i,cur.l,cur.t-1,rmq(cur.l,cur.t-1)));if(cur.t+1<=cur.r)que.push(DAT(cur.i,cur.t+1,cur.r,rmq(cur.t+1,cur.r)));}
}
int main()
{read(n,k);read(L,R);for1(i,n)read(sum[i]);for1(i,n)sum[i]+=sum[i-1];rmq_init();solve();printf("%lld\n",ans);
}

这篇关于NOI2010...BZOJ2006 超级钢琴贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！