题目描述
小 L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。
游戏中有一个叫做 “LCT” 的挑战,它的规则是这样子的:现在有一个 NN 个点的树(Tree),每条边有一个整数边权 vi" role="presentation">viviv_i,若 vi≥0" role="presentation">vi≥0vi≥0v_i \ge 0,表示走这条边会获得 vi" role="presentation">viviv_i的收益;若 vi&
【题目描述】
小H最近迷上了一个分隔序列的游戏。在这个游戏里,小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列,小H需要重复k次以下的步骤:
1.小H首先选择一个长度超过1的序列(一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列);
2.选择一个位置,并通过这个位置将这个序列分割成连续的两个非空的新序列。
每次进行上述步骤之后,小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式,使得k轮之后,小H的总得分最大。
【输入】
输入第一行包含两个整数n,k(k+1≤n)。
第二行包含n