优化动态规划式子，\(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)\) 的递推。
例题：