Description
Solution
斜率优化DP首题，多写一点吧。
Step 1 写出DP方程
设(f_i)为(i)点时的最优方案，(s_i)为(i)点(C_i)前缀和，则有(f_i = min{f_j+(i-j-1+s_i-s_j-l)^2mid 0le j < i-1})。
Step 2 证明决策单调性
不要被这个“决策单调性”给唬住，其实就是证明：若在计算(f_i)的时候，选(j)比选(k)好，那么之后永远都有选(j)比选(k)好。
证明：
首先设(t_x = s_x+x,c = l+1)且(j > k)，选(j)比选(k)好，简化之后的表示
(f_j+(t_i-t_j-c)^2 < f_k + (t_i-t_j-c)^2)
(Leftrightarrow f_j+t_i^2+t_j^2+c^2-2t_it_j+2t_jc-2t_ic < f_k+t_i^2+t_k^2+c^2-2t_it_k+2t_kc-2t_ic)
(Leftrightarrow f_j+t_j^2-2t_it_j+2t_jc - f_k - t_k^2 + 2t_it_k - 2t_kc < 0)
(Leftrightarrow f_j + t_j^2+ 2t_jc - f_k - t_k^2 - 2t_kc < 2t_it_j - 2t_it_k)
由于(t)是单调上升的，所以(2t_j-2t_k>0)，所以
(mbox{原式}Leftrightarrow displaystylefrac{f_j + t_j^2+ 2t_jc - f_k - t_k^2 - 2t_kc}{2t_j - 2t_k} < t_i)
又因为(t)是单调上升的，所以一旦满足了这个条件，选(j)永远比选(k)好。
Step 3 构造斜率形式
这一步其实就是看分子分母，化出和(j)，(k)有关的式子，就可以了。
设(F_x = t_x^2+f_x+2ct_x)，(G_x=2t_x)
则原式可化成(displaystylefrac{F_j-F_k}{G_j-G_k}<t_i)，由于(G)单调增，不等号左边的式子（上下同乘(-1)后）就是在平面(GOF)上的一条直线((k,j))的斜率（记为(K_{k,j})）。
Step 4 证明斜率单调
设(x, y, z)满足(x < y < z)，且(K_{x,y}>K_{y,z})，则选(y)不可能更优。
证明：考虑反证法，若(y)优于(x)和(z)，则有：
(displaystylefrac{F_z-F_y}{G_z-G_y}>t_i)（这个式子其实是将Step2中的(j>k)反过来推出来的）
和(displaystylefrac{F_y-F_x}{G_y-G_x}<t_i)
即(K_{y,z}=displaystylefrac{F_z-F_y}{G_z-G_y}>displaystylefrac{F_y-F_x}{G_y-G_x}=K_{x,y})与题设矛盾。
这里应该先考虑(y)优于(x)和(z)，推出式子后得出斜率的单调结论。
Step 5 单调队列优化DP
单调队列是一个双端队列。
由于Step2,3，若在(i)处有(K_{k,j}<t_i)((k, j)位于队首)，则应该令(k)出队，反复执行直至队列中只有一个元素或不满足条件为止，此时队首即为决策。
当计算出(f_i)后，利用Step4的结论，在队尾不断出队直至直至队列中只有一个元素或不满足条件为止，并将(i)放入队尾。
Code
#include <cstdio>
#include <cmath>
typedef long long LL;
const int N = 50000 + 10;
const double eps = 1e-10;
int n, l;
LL C[N], f[N], s[N], t[N], c, F[N], G[N];
int q[N], qhd, qtl;
inline double K(int x, int y) {
return 1.0 * (F[x] - F[y]) / (G[x] - G[y]);
}
inline int dcmp(double x) {
if (fabs(x) < eps) return 0;
else if (x < 0) return -1;
else return 1;
}
int main () {
// input
scanf("%d%d", &n, &l);
for (int i = 1; i <= n; ++i) scanf("%lld", &C[i]);
// init
c = l + 1;
for (int i = 1; i <= n; ++i) {
s[i] = s[i-1] + C[i];
t[i] = s[i] + i;
G[i] = 2 * t[i];
}
// dp
f[0] = 0;
q[qtl++] = 0;
for (int i = 1; i <= n; ++i) {
while (qhd < qtl - 1) {
if (dcmp(K(q[qhd], q[qhd+1]) - t[i]) == -1) qhd++;
else break;
}
int j = q[qhd];
f[i] = f[j] + (t[i] - t[j] - c) * (t[i] - t[j] - c);
F[i] = t[i] * t[i] + f[i] + 2 * c * t[i]; // mark
while (qhd < qtl - 1) {
if (dcmp(K(q[qtl-1], q[qtl-2]) - K(q[qtl-1], i)) == 1) qtl--;
else break;
}
q[qtl++] = i;
}
printf("%lld
", f[n]);
return 0;
}
Note
这个题是我写的斜率优化DP的第一题，感觉斜率优化很模板化，只需要一点点推就行了，要注意的一点是斜率优化的复杂度(O(n))的，另外，演草时要好好写字，否则真的会看不清...（例如mark处我一开始写的是+t[i]）