只是 DP 优化罢了，其他乱七八糟的 DP 根本不会。
全文只是我自己的理解，有逻辑上的错误请指出来 qwq
斜率优化 DP
斜率优化的流程是这样的。
首先列出 DP 式子，接着钦定两个在当前位置之前的变量。
形式化地，当前转移目标为 \(i\)，钦定 \(1 \le j_1<j_2<i\)。
接着钦定 \(j_1<j_2\) 且 \(j_2\) 优于 \(j_1\)。
此处的 \(j_1,j_2\) 代表由 \(j \rightarrow i\) 的决策转移点。
因为 DP 题目一定具有最优子结构，所以最优的 \(dp_i\) 必定由最优的 \(dp_j\) 转移而来。
这里每一层决策顺次下来，显然具有答案单调性。
大家都做过滑动窗口吧，思想其实差不多。
所以，这时候就可以利用单调队列和一定的安排次序来使得答案最优化。
目的：在保证下标单调性的同时探究什么因素导致了答案的单调性。
这个因题目而异，但万变不离其宗：函数式思想和单调性。
P3195 [HNOI2008] 玩具装箱：斜率优化入门。
这道题可以具体展现斜率优化的流程。
第 1 步，列出 DP 转移方程。
假设目前已经 DP 完了 \([1,j]\)，要从 \(j\) 直接转移到 \(i\)。
那么新产生的段就是 \([j+1,i]\)。根据定义，\(dp_i=\max\{dp_i,dp_j+(x-L)^2\}\)。
此处 \(x=i-(j+1)+\sum\limits_{k=j+1}^iC_k=i-j-1+\sum\limits_{k=j+1}^iC_k\)。
这样暴力转移当然是 \(O(N^3)\) 的。
但是看到区间静态和，直接优化掉一维循环，设 \({sum}_i=\sum\limits_{j=1}^i C_j\)。
那么有 \(x=i-j-1+{sum}_i-{sum}_j\)。
那么朴素 \(O(N^2)\) DP 转移方程即为
\[dp_i=\max\{dp_i,dp_j+(i-j-1+{sum}_i-{sum}_j-L)^2\} \]看到 \(1 \le N \le 5 \times 10^4\)，考虑优化。
第 1.5 步，让式子看起来更舒服。
真不是开玩笑。如果看到一堆不知所云的项，对我来说，斜率优化真没办法推。
当然，如果你的脑子非常好使，当然不需要这些乱七八糟的东西。
下面来设置一些函数，用来替换式子中的某一些项。
比如，这里使用 \(f(i)\) 来替换 \({sum}_i+i\)。
那么原式化为
\[dp_i=\max\{dp_i,dp_j+(f(i)-f(j)-1-L)^2\} \]嗯，看起来非常舒服。
第 2 步，拆式子。
这时候我们钦定的 \(j_1\) 和 \(j_2\) 派上用场了。
在此设 \(1 \le j_1<j_2<i \le N\)，且 \(j_2\) 优于 \(j_1\)。
这道题里面的“优”就是代价小。
那么翻译成人话就是
\[dp_{j_2}+(f(i)-f(j_2)-1-L)^2 \le dp_{j_1}+(f(i)-f(j_1)-1-L)^2 \]这时候，有技巧地拆开。
将 \(f(i)-f(j)-1-L\) 拆成两半，一半含有 \(i\)，另一半是剩下所有项。
这里我拆成了 \(f(i)\) 和 \(-(f(j)+1+L)\)。
那么可以开始拆了。
\[dp_{j_2}+f(i)^2-2\times f(i) \times (f(j_2)-1-L) + (f(j_2)-1-L)^2 \le dp_{j_1}+f(i)^2-2\times f(i) \times (f(j_1)-1-L) + (f(j_1)-1-L)^2 \]接着把含有 \(i\) 的丢到左边，剩下的移项到右边。
\[2 \times f(i) \times ((f(j_1)-1-L)-(f(j_2)-1-L)) \le (dp_{j_1}+(f(j_1)+L+1)^2) - (dp_{j_2}+(f(j_2)+L+1)^2) \]合并一下
\[2 \times f(i) \times (f(j_1)-f(j_2)) \le (dp_{j_1}+(f(j_1)+L+1)^2) - (dp_{j_2}+(f(j_2)+L+1)^2) \]这里观察到右边下标有相同的地方，令 \(g(i)=(f(i)+L+1)^2\)。
那么看到
\[2 \times f(i) \times (f(j_1)-f(j_2)) \le (dp_{j_1}+g(j_1))-(dp_{j_2}+g(j_2)) \]现在左边应变为只含 \(i\) 的项（因为要探究转移目标为 \(i\) 时答案的规律）
两边同除以 \((f(j_1)-f(j_2))\) 得到
\[2 \times f(i) \ge \dfrac{(dp_{j_1}+g(j_1))-(dp_{j_2}+g(j_2))}{f(j_1)-f(j_2)} \]（因为 \(f(i)\) 单调递增，\(f(j_1)-f(j_2) < 0\)，中间要变号）
观察到右侧 \(j_1,j_2\) 下标其实是对应的，想到求一次函数的斜率。
\[k=\dfrac{\Delta y}{\Delta x} \]这不一个形式。。。
所以将 \(dp_i+g(i)\) 视作 \(y_i\)，右边就是两个决策点之间的斜率。
回到定义，\(j_2\) 优于 \(j_1\)。
那么我们知道，一个决策点 \(j_2\) 优于另一个决策点 \(j_1\) 的条件就是
其实因为 \(j_2>j_1\)，写成这样更严谨：
\[2 \times f(i) \ge \dfrac{(dp_{j_2}+g(j_2))-(dp_{j_1}+g(j_1))}{f(j_2)-f(j_1)} \]这玩意儿可以拿单调队列优化。
由于 \(f(i)\) 单调递增，每一次找到的第一个符合条件的 \(j\)，必定是最优决策。
随着 \(f(i)\) 单调递增，斜率显然也单调递增。
最后，如果有不符合单调递增规律的尾元素，直接删掉，最后插入 \(i\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 10;
int n, L, h, t, q[N], sum[N], dp[N];
inline int f(int x) { return sum[x] + x; }
inline int g(int x) { return (f(x)+L+1) * (f(x)+L+1); }
inline double slope(int j1, int j2) {
return 1. * ((g(j2)+dp[j2]) - (g(j1)+dp[j1])) / (f(j2)-f(j1));
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> L; h = t = 1;
for (int i = 1; i <= n; ++i)
cin >> sum[i], sum[i] += sum[i-1];
for (int i = 1; i <= n; ++i) {
while (h < t && 2 * f(i) >= slope(q[h], q[h+1])) ++h;
dp[i] = dp[q[h]] + (f(i)-f(q[h])-L-1) * (f(i)-f(q[h])-L-1);
while (h < t && slope(q[t], i) <= slope(q[t-1], q[t])) --t;
q[++t] = i;
}
cout << dp[n] << endl;
return 0;
}