斜率优化
发布时间: September 3, 2018
Categories: 学习笔记 题解
其实这一篇文章是为了补上一篇文章的坑...斜率优化是决策单调性优化的一中特殊形式.
你可以连续的输出一些单词,定义每个单词的度为 $ a[i] $ ,则输出 $ i $ 到 $ j $ 的词的代价是 $(\Sigma^k _{i=1} a[i])^2 + M$.单词不能打乱顺序输出.
其中 $ N \leq 500000,M \leq 1000 $
这是一道基本的斜率优化的题目.
动态规划的式子我们都很好推,设 $ f_i $ 表示输出前 $i$ 个单词的最小代价,有转移方程
$$ f_i = min{f_j +