标签 - 斜率优化

? 解题记录 ? ? 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
? 解题记录 ? ? 洛谷 ? ? 动态规划 ? ? 斜率优化 ? ? 凸包 ? ? stl ?    2018-11-04 15:44:33    671    0    0
Description 小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券:A纪念券(以下简称A券)和 B纪念券(以下 简称B券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动, 两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A券 和 B券 的 价值分别为 AK 和 BK(元/单位金券)。为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法 。比例交易法分为两个方面:(a)卖出金券:顾客提供一个 [0,100] 内的实数 OP 作为卖出比例,其意义为:将  OP%
? 解题记录 ? ? HDU ? ? 动态规划 ? ? 斜率优化 ?    2017-10-14 21:31:29    528    0    0
Covered WalkwayTime Limit: 30000/10000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 1548    Accepted Submission(s): 623 Problem Description Your university wants to build a new walkway, and they want at least part of it t