A. Alice and Books
【题目大意】
\(n\) 本书,编号为 \(1\) 到 \(n\),价值为 \(a_1\) 到 \(a_n\)。将这些书分成两堆,你获得每堆编号最大的书的价值。求可以获得的最大的价值。
【解题思路】
无论怎样,编号为 \(n\) 的书不管在那一堆都是编号最大的,所以一定会有它的价值。
那么我们另外一堆中可以获得剩下 \(n-1\) 本书中价值最大的。具体地,\(1\) 到 \(n - 1\) 中最大价值的编号为 \(i\),那么 \(1\) 到 \(i\) 放一堆,\(i + 1\) 到 \(n\) 放一堆,答案为 \(a_i + a_n\),它一定是最优的。
B. New Bakery
【题目大意】
一个长度为 \(n\) 的序列,前 \(k\) 项为公差为 \(-1\) 的,首项为 \(b\) 的等差数列。后面的数全是 \(a\)。给定了 \(n\)、\(a\)、\(b\),求序列所有数的和的最大值。
【解题思路】
在最优解中,显然,前 \(k\) 项的等差数列中,每一项都应该比 \(a\) 大,否则将其换成 \(a\) 会更优。所以我们只需要令 \(k = b - a\),这样,前 \(k\) 项都大于 \(a\),并且等差数列第 \(k + 1\) 小于 \(a\),这样是最优的。
最后等差数列求和公式出来即可。注意 \(k\) 的边界条件。