HBC20193[JSOI2011]柠檬题解 （贝壳变成柠檬的方法）

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

Flute 很喜欢柠檬，它准备了一串用树枝串起来的贝壳，打算用一种魔法把贝壳变成柠檬，贝壳一共有 N (1 ≤ N ≤ 100,000) 只，按顺序串在树枝上， 为了方便，我们从左到右给贝壳编号 1..N，每只贝壳的大小不一定相同， 贝壳 i 的大小为 si(1 ≤ si ≤ 10,000)，变柠檬的魔法要求，Flute 每次从树枝一端取下一小段连续的贝壳。

Flute 很喜欢柠檬。它准备了一串用树枝串起来的贝壳，打算用一种魔法把贝壳变成柠檬。贝壳一共有 N (1 ≤ N   ≤ 100,000) 只，按顺序串在树枝上。 为了方便，我们从左到右给贝壳编号 1..N。每只贝壳的大小不一定相同， 贝壳 i 的大小为 si(1 ≤ si ≤ 10,000)。变柠檬的魔法要求，Flute 每次从树枝一端取下一小段连续的贝壳，并选择一种贝壳的大小 s0。 如果这一小段贝壳中 大小为 s0 的贝壳有 t 只，那么魔法可以把这一小段贝壳变成 s0t^2 只柠檬。Flute 可以取任意多次贝壳，直到树枝上的贝壳被全部取完。 各个小段中，Flute 选择的贝壳大小 s0 可以不同。而最终 Flute 得到的柠檬数，就是所有小段柠檬数的总和。Flute 想知道，它最多能用这一串贝壳 变出多少柠檬。请你帮忙解决这个问题。

标签： HBC20193[JSOI2011]柠檬题解