标签 - 带权二分

? 解题记录 ? ? LOJ ? ? 带权二分 ? ? 动态规划 ?    2018-12-10 09:18:19    331    0    0
题目描述 小 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&
? 解题记录 ? ? BZOJ ? ? 斜率优化 ? ? 带权二分 ? ? 动态规划 ?    2018-11-04 16:21:53    721    0    0
【题目描述】 小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