HBC17626[NOI2010]超级钢琴题解

季陌殇算法基础篇 2023-11-21 18:59:02 62 0

想要成为编程高手？那就来试试全网最全C++题库，让您在练习中快速成长。

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

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