题目链接其实这一篇文章是为了补上一篇文章的坑…斜率优化是决策单调性优化的一中特殊形式。题目描述你可以连续的输出一些单词，定义每个单词的度为 $ a[i] $ ,则输出 $ i $ 到 $ j $ 的词的代价是 $(\Sigma^k _{i=1} a[i])^2 + M$。单词不能打乱顺序输出。其中 $ N \leq 500000,M \leq 1000 $
写一些简单的 1D/1D 的决策单调性优化...这种决策单调性优化的过程：列出方程 $\to$ 打表发现决策单调性 $\to$ 套单调队列/二分我们以一些例题为例：
这道题甚至不如 T2 难...放在 T3 真的合适吗...题目链接题目描述一张无向带权图，需要选择 $ N $ 次。每次在两个点 $ c_i,d_i $ 中，有 $ p_i $ 的概率选择点 $ d_i $，有 $ 1-p_i $ 的概率选择点 $ c_i $ ，每次选择相互独立。至多能选 $ M $ 次 $ d $ 类节点现在求出所有选择的路线方案中的最小期望值。