[db:标题]

优化动态规划式子，\(1\leq i\leq n\)，其中 \(a_i\) 和 \(b_i\) 都是预先给定的常数： \[f(i)=\max_{1\leq k\leq i} f(k-1)+|a_i-a_k|+|b_i-b_k| \] 期望复杂度：\(O(n)\)。 解答：lcw's trick 注意到 \(|x-y|=\max\{x-y,y-x\}\)，于是考虑令 \[\begin{aligned}g_{00}(i)&=\max_{1\leq k\leq i} f(k-1)-a_k-b_k\\g_{01}(i)&=\max_{1\leq k\leq i} f(k-1)-a_k+b_k\\g_{10}(i)&=\max_{1\leq k\leq i} f(k-1)+a_k-b_k\\g_{11}(i)&=\max_{1\leq k\leq i} f(k-1)+a_k+b_k\end{aligned} \] 于是，显然有 \(O(1)\) 递推式 \[\begin{aligned}g_{00}(i)&=\max\{g_{00}(i-1),f(i)-a_i-b_i\}\\g_{01}(i)&=\max\{g_{01}(i-1),f(i)-a_i+b_i\}\\g_{10}(i)&=\max\{g_{10}(i-1),f(i)+a_i-b_i\}\\g_{11}(i)&=\max\{g_{11}(i-1),f(i)+a_i+b_i\}\end{aligned} \] 另一方面，我们有 \[f(i)=\max\left\{\begin{aligned}&g_{00}(i-1)+a_i+b_i,\\&g_{01}(i-1)+a_i-b_i,\\&g_{10}(i-1)-a_i+b_i,\\&g_{11}(i-1)-a_i-b_i\end{aligned}\right\} \] 这立即得到了一个 \(O(n)\) 的递推。 例题： CF1859E 参考实现：218582129