2006: [NOI2010]超級鋼琴

Time Limit:?20 Sec? Memory Limit:?512 MB
Submit:?4292? Solved:?2195
[Submit][Status][Discuss]

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，表示按編號從小到大每個音符的美妙度。 N<=500,000 k<=500,000 -1000<=Ai<=1000,1<=L<=R<=N且保證一定存在滿足條件的樂曲

Output

只有一個整數，表示樂曲美妙度的最大值。

題解：

?????? 就是求長度在[L,R]之內的前n大區間的和；

???????? 維護前綴和sum[i] – sum[j]?? (j<i , L<=i-j<=R ) 的前n大；

???????? 有L,R的限制，設計狀態(i,j,k)表示可以選取的值為sum[i] – sum[j –> k] ， sum[i]一定，可以用rmq得到此時的最大值，對于所有右端點i把(i,i-R,i-L) 一起丟進優先隊列里面，每次取出最大值，如果選中了(i,j,k)，且最大值為sum[i]-sum[p] ，就把(i,j,p-1),(i,p+1,k)重新放回優先隊列；

???????

轉載于:https://www.cnblogs.com/Paul-Guderian/p/10092804.html

總結

以上是生活随笔為你收集整理的【bzoj2006】【NOI2015】超级钢琴的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。