本文主要是介绍C++类型题整理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

【营业记录】时光流韵

也许是一枚能够跨越时空的护符，是先闻其声，或是余音绕梁。

关键词：DP

(1) 内容概要

• 费用提前计算
• 单调栈
• 单调队列
• 斜率优化

(2) 费用提前计算

让我们以 P2365 任务安排 为例。

下文中题目里的费用系数我使用 c_ici​ 表示。且令 sunTsunT 为 tt 的前缀和，sumCsumC 为 cc 的前缀和。

我们令 f[i,j]f[i,j] 表示把前 ii 个任务分为 jj 批的最小费用。得出：

f[i,j]=min_{0\le k<i}\{f[k,j-1]+(s*j+sumT[i])*(sumC[i]-sumC[k])\}f[i,j]=min0≤k<i​{f[k,j−1]+(s∗j+sumT[i])∗(sumC[i]−sumC[k])}

这样是 O(n^3)O(n3)。

然后考虑一个思想费用提前计算。我们发现每次转移时 jj 的存在意义是算出 s*js∗j 然后算出时间。然后我们把这个费用提前，在每次转移的时候为以后的费用考虑好，机器为这次启动花费的 ss 会累加到后面。所以现在可以舍去一维，令 f[i]f[i] 表示把前 ii 个任务分成若干批最小费用，得：

f[i]=min_{0\le j<i}\{f[j]+(sumC[i]-sumC[j])*sumT[i]+s*(sumC[N]-sumC[j])\}f[i]=min0≤j<i​{f[j]+(sumC[i]−sumC[j])∗sumT[i]+s∗(sumC[N]−sumC[j])}

这是 O(n^2)O(n2)。然后这题暂时是做完了。简单的小练习：

• P2466 [SDOI2008]Sue的小球
• P1220 关路灯

(3) 单调栈

单调栈，就是要维护一个栈，单调递增或递减。一般地，放入元素时，如果栈顶的元素不符合单调递增（或递减），那就把它弹出，再查栈顶。直到符合或栈空了，再把元素放入。

线性求每个数两侧比它大（或小）的数的位置。

典型的应用是 柱状图中最大的矩形，用单调栈维护每个数两侧比它小的数的位置。

P2422 良好的感觉 同理，只需要一个前缀和优化，就是单调栈的模板题了。

(4) 单调队列

单调队列，就是要维护一个队列，单调递增或递减。一般地，放入元素时，先弹出末尾无效元素。如果队列首的元素不符合单调递增（或递减），那就把它弹出，再查队列首。直到符合或队列空了，再把元素放入。

队列中的元素其对应在原来的列表中的顺序必须是单调递增的。队列中元素的大小必须是单调递增减/甚至是自定义也可以）。

f(x)=opt_{i=bound[x]}^{x-1}(const[i])f(x)=opti=bound[x]x−1​(const[i])

对于这样一类动态规划问题，我们可以运用单调队列来解决： 其中 bound[x]bound[x] 随着 xx 单调不降，而 const[i]const[i] 则是可以根据 ii 在常数时间内确定的唯一的常数。

• P1886【模板】单调队列

• P2629 好消息，坏消息 考虑区间 DP 里的终点思想破环成链，套上单调队列。

• P6040 课后期末考试滑溜滑溜补习班 把 DP 式子推出来以后容易发现可以单调队列优化，这一类的套路题目比较多。

(5) 斜率优化

斜率优化要解决的问题是求 dp[i]=a[i]*b[j]+c[i]+d[j]dp[i]=a[i]∗b[j]+c[i]+d[j]。在最基础的形式中，a[i],b[j]a[i],b[j] 单调递增。如果 a[i]a[i] 不单调递增也没事，我们之后再讨论。

移项：-a[i]b[j]+dp[i]-c[i]=d[j]−a[i]b[j]+dp[i]−c[i]=d[j]。

把 b[j]b[j] 看作 xx ，把 d[j]d[j] 看作 yy，把 -a[i]−a[i] 看作 kk

kx+dp[i]-c[i]=ykx+dp[i]−c[i]=y此直线过 (x,y)(x,y) 且斜率已知为 kk ，要求截距最小。维护一个凸壳。对于每个 ii，要求的是第一个满足 slope(P_j,P_{j+1})>kslope(Pj​,Pj+1​)>k 的。

一般斜率优化单调队列维护即可。若 aa 无单调性，用二分查找；若 bb 无单调性，用平衡树。

回到 P2365 任务安排，发现这个式子符合斜率优化。

f[i]=f[j]+(sumC[i]-sumC[j])*sumT[i]+s*(sumC[N]-sumC[j])f[i]=f[j]+(sumC[i]−sumC[j])∗sumT[i]+s∗(sumC[N]−sumC[j])

f[i]=f[j]+sumC[i]*sumT[i]-sumC[j]*sumT[i]+sumC[N]*s-sumC[j]*sf[i]=f[j]+sumC[i]∗sumT[i]−sumC[j]∗sumT[i]+sumC[N]∗s−sumC[j]∗s

f[i]=-sumC[j]*sumT[i]+(f[j]-sumC[j]*s)+(sumC[i]*sumT[i]+sumC[N]*s)f[i]=−sumC[j]∗sumT[i]+(f[j]−sumC[j]∗s)+(sumC[i]∗sumT[i]+sumC[N]∗s)

(f[i]-sumC[i]*sumT[i]-sumC[N]*s)+sumC[j]*sumT[i]=f[j]-sumC[j]*s(f[i]−sumC[i]∗sumT[i]−sumC[N]∗s)+sumC[j]∗sumT[i]=f[j]−sumC[j]∗s

b+kx=yb+kx=y

操作步骤如下：

1. 对于队首 while(slope(P_{head},P_{head+1})<k) head++while(slope(Phead​,Phead+1​)<k)head++；

2. 队首为最优，计算 dp[i]dp[i]；

3. 队尾 while(slope(P_{tail-1},P_{tail})>slope(P_{tail-1},P_{i})) tail--while(slope(Ptail−1​,Ptail​)>slope(Ptail−1​,Pi​))tail−−；

4. 在队尾加入 P_iPi​。

考虑一些问题：

• P3195 [HNOI2008]玩具装箱

• P5017 摆渡车 列出 DP 方程后展开直接优化。

• P6047 丝之割 先把弦转为为二维平面上的点，去掉无用状态后发现 DP 方程可以斜率优化。注意，这里的斜率是负数。

你需要注意：

• 使用单调队列的条件是斜率满足单调性质而不是点满足单调性质，如果不满足单调性质可以换用单调栈内二分，复杂度多一个 \loglog。

• 由于两个点的 xx 坐标有可能相同所以需要特判成 \text{inf}inf，如果不特判也许会变成 \text{-inf}-inf。

这篇关于C++类型题整理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！