CodeforcesLuogu分析容易想到一个 DP。设 $dp_u$ 表示 $u$ 跳到叶子节点的最小花费,显然有转移可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑李超线段树,转移时直接查询对应位置的最小值,然后向上合并即可。可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑...
LuoguBZOJ分析对于第 $i$ 个计划,第 $x$ 天的收益为 $s_i+(x-1)p_i$ 。显然是一次函数的形式。那么就是李超线段树的板子了。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstrin...