$dp$模板

数位$dp$

咕咕咕

单调队列优化

• 总结了一个模板,其中$lst$表示还未加入的决策点的最左端的位置(以维护不上升为例),$L(i),R(i)$只是与$i$(这里的$i$指的是外层的维度,并不一定是$i$)有关的左界和右界,$calc(j)$是只与$j$有关的计算函数,$w(i)$是只与$i$有关的计算函数

• 注意 $f[i]$转移时极易忘记判断队列是否为空

for(int i = 1;i <= n; ++i) {
    while(lst < L(i)) ++lst
    for(;lst <= R(i); ++lst) {
        while(l <= r && calc(q[r]) < calc(lst)) --r;
        q[++r] = lst;
    }
    while(l <= r && q[l] < L(i)) ++l;
    if(l <= r) f[i] = calc(q[l])+w(i);//再次注意 此处if(l <= r)判断队是否为空极易忘!!!!!! 
}

斜率优化

咕咕咕