NOI2010 超级钢琴
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
只有一个整数，表示乐曲美妙度的最大值。
Sample Input
4 3 2 332
-6
8
Sample Output
11「样例说明」
共有5种不同的超级和弦：音符1 ~ 2，美妙度为3 + 2 = 5
音符2 ~ 3，美妙度为2 + (-6) = -4
音符3 ~ 4，美妙度为(-6) + 8 = 2
音符1 ~ 3，美妙度为3 + 2 + (-6) = -1
音符2 ~ 4，美妙度为2 + (-6) + 8 = 4
最优方案为：乐曲由和弦1，和弦3，和弦5组成，美妙度为5 + 2 + 4 = 11。
共有5种不同的超级和弦：音符1 ~ 2，美妙度为3 + 2 = 5
音符2 ~ 3，美妙度为2 + (-6) = -4
音符3 ~ 4，美妙度为(-6) + 8 = 2
音符1 ~ 3，美妙度为3 + 2 + (-6) = -1
音符2 ~ 4，美妙度为2 + (-6) + 8 = 4
最优方案为：乐曲由和弦1，和弦3，和弦5组成，美妙度为5 + 2 + 4 = 11。
题解
oimaster:
用三元组(i, l, r)表示右端点为i，左端点在[l, r]之间和最大的区间（[l, r]保证是对于i可行右端点区间的一个子区间），我们用堆维护一些这样的三元组。堆中初始的元素为每个i，并且[l, r]为这个i可行左端点的区间。假如某次最大值为(i, l, r)，并且j为那个和最大区间的左端点，那么需要往堆中加入两个三元组(i, l, j-1)和(i, j+1, r)。对于一个三元组，计算对应最大和的问题实际就是一个RMQ问题，可以通过Sparse Table在O(NlogN) – O(1)的时间内解决。这个算法的总时间复杂度为O(NlogN + K log(N+K))
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #define mp(a,b,c,d) (data){a,b,c,d} #define inf 1000000000 #define ll long long #define N 500005 using namespace std; inline int read() { int 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();} return x*f; } struct data{int i,l,r,t;}; int bin[20],Log[N]; int n,K,L,R; int a[N],mx[N][20]; ll ans; void pre() { Log[0]=-1;for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1; for(int i=1;i<=n;i++)mx[i][0]=i; for(int i=n;i;i--) for(int j=1;j<=18;j++) if(i+bin[j]-1<=n) { int t1=mx[i][j-1],t2=mx[i+bin[j-1]][j-1]; mx[i][j]=a[t1]>a[t2]?t1:t2; } else break; } inline int query(int l,int r) { if(l==r)return l; int t=Log[r-l+1]; int t1=mx[l][t],t2=mx[r-bin[t]+1][t]; return a[t1]>a[t2]?t1:t2; } inline bool operator<(data x,data y) { return a[x.t]-a[x.i-1]<a[y.t]-a[y.i-1]; } void solve() { priority_queue<data,vector<data> >q; for(int i=1;i<=n;i++) if(i+L-1<=n) { int t=min(n,i+R-1); q.push(mp(i,i+L-1,t,query(i+L-1,t))); } for(int i=1;i<=K;i++) { data t=q.top();q.pop(); ans+=a[t.t]-a[t.i-1]; if(t.t-1>=t.l)q.push(mp(t.i,t.l,t.t-1,query(t.l,t.t-1))); if(t.t+1<=t.r)q.push(mp(t.i,t.t+1,t.r,query(t.t+1,t.r))); } } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; n=read();K=read();L=read();R=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)a[i]+=a[i-1]; pre(); solve(); printf("%lld",ans); return 0; } |
计数器 9786445
OI 课件=>
OI 课件=>
orz
orz hzwer