Codeforces Round 351 E. Levels and Regions(斜率优化dp)

题意: $将N\le 2\times 10^5个关卡划分成M\le min(50, n)个组,组内关卡连续,t_i\le 10^5$$定义游戏规则,每次选择第一个未全部完成的组,假设组处于关卡区间[l, r]$$选择到组内第一个未完成的关卡的概率p_i=\frac{t_i}{\sum_{i=l}^i t_i}$$求怎样划分组使得通过所有组的期望打关卡次数最小,求这个次数,误差小于10^{-4}$     Read more
TaoSama's avatar
TaoSama May 11, 2016

HDU 2829 Lawrence(斜率优化dp)

题意: $N\le 1000个点,点权c_i \le 100,划分成0\le M<N个连续段$$每段的权值w(x, y)=\sum_{i=x}^{y-1}\sum_{j=i+1}^y c_i\cdot c_j$$求一个划分使得段权值和最小,输出这个权值和$     Read more
TaoSama's avatar
TaoSama May 11, 2016

斜率优化dp小结

Ⅰ. 斜率优化认知 这东西英文名叫$Convex Hull Trick (CHT)$ 主要优化形如$f_i = min\{ f_j + cost(j+1, i) \}的这种dp$ 由于等号右边的式子并不能$O(1)$计算,所以我们需要一些技巧来优化     Read more
TaoSama's avatar
TaoSama May 11, 2016