$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)判断队是否为空极易忘!!!!!! 
}

斜率优化

咕咕咕