发现原式转化为 \(b_i=\min\{y_j-k_i\times x_j\}\) 。
看上去有那么亿点点的像 \(y=kx+b\) 呢……
考虑这个求 \(b_i\) 的最小值的过程，就是在最小化直线的截距 。把 \((x_j,y_j)\) 看作平面上的一个点，现在有一条斜率为 \(k_i\) 的直线，从下往上找（最小化），找到的第一个点就是转移决策点 。
实际上 ， 只需维护下凸壳的那些点 。
对于本题，\(k_i\) 随 \(i\) 的增大而增大 ， 所以可以用单调队列进行维护 。
const int N = 50010;int n, c[N], l = 1, r = 0;;ll sum[N], s[N], f[N], L;ll Get(int x) { return f[x] + (sum[x] + L) * (sum[x] + L);}long double slope(int x, int y) { return (Get(y) - Get(x)) * 1.0 / (sum[y] - sum[x]);}int main() { n = read(), L = read() + 1; for (int i = 1; i <= n; i++) c[i] = read(); for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + c[i] + 1; s[++r] = 0; for (int i = 1; i <= n; i++) {while (l < r && slope(s[l], s[l + 1]) <= (sum[i] << 1)) l++;f[i] = f[s[l]] + (sum[i] - sum[s[l]] - L) * (sum[i] - sum[s[l]] - L);while (l <= r && slope(s[r - 1], s[r]) >= slope(s[r - 1], i)) r--;s[++r] = i;}printf("%lld\n", f[n]); return 0;}N. 参考内容DP优化 - zuytong
单调队列优化DP - superPG
【dp优化 | 各种dp优化方式例题精选】
推荐阅读
- 梦幻西游搬砖赚钱方式（梦幻西游搬砖如何月入3000)
- 灵域境界等级划分_灵域各种等级势力介绍
- 基于PL022 SPI 控制器 海思3516系列芯片SPI速率慢问题深入分析与优化
- 我的世界创造模式怎么骑马，骑马方式详解（在我的世界里面怎么教我们骑马)
- 云计算_OpenStack
- zip怎么设置默认打开方式（怎么更换zip打开方式)
- Vue3 SFC 和 TSX 方式调用子组件中的函数
- 九重试炼免广告卷获取方式是什么
- 怎么在线预览.doc，.docx，.ofd，.pdf，.wps，.cad文件以及Office文档的在线解析方式。
- 京东云TiDB SQL优化的最佳实践