企业官网建设流程全解析

算法介绍
在平时的 DP 过程中，我们可能会遇到这样的 DP 式子：

�
�
�

min
⁡
�

�
−
�
�
−
�
(
�
�
�
+
�
�
×
�
�
+
�
�
+
�
�
+
�
)
dp
i
​

j=i−x
min
i−y
​
(dp
j
​
+a
i
​
×b
j
​
+c
i
​
+d
j
​
+M)
单调队列优化 DP 拼劲全力无法战胜，只能请它大哥出场了。

推导一
动态规划当然要考虑最优决策点的位置呀！所以我们假设现在有
�
1
,
�
2
(
�
1
<
�
2
)
j
1
​
,j
2
​
(j
1
​
<j
2
​
) 两个决策点，如果
�
2
j
2
​
更优秀，应该满足的条件是酱紫的：

�
�
�
2
+
�
�
×
�
�
2
+
�
�
+
�
�
2
+
�
≤
�
�
�
1
+
�
�
×
�
�
1
+
�
�
+
�
�
1
+
�
�
�
�
2
+
�
�
×
�
�
2
+
�
�
2
≤
�
�
�
1
+
�
�
×
�
�
1
+
�
�
1
−
�
�
×
(
�
�
1
−
�
�
2
)
≤
(
�
�
�
1
+
�
�
1
)
−
(
�
�
�
2
+
�
�
2
)
dp
j
2
​

​
+a
i
​
×b
j
2
​

​
+c
i
​
+d
j
2
​

​
+M
dp
j
2
​

​
+a
i
​
×b
j
2
​

​
+d
j
2
​

​

−a
i
​
×(b
j
1
​

​
−b
j
2
​

​
)
​

≤dp
j
1
​

​
+a
i
​
×b
j
1
​

​
+c
i
​
+d
j
1
​

​
+M
≤dp
j
1
​

​
+a
i
​
×b
j
1
​

​
+d
j
1
​

​

≤(dp
j
1
​

​
+d
j
1
​

​
)−(dp
j
2
​

​
+d
j
2
​

​
)
​

如果
�
�
1
−
�
�
2
≠
0
b
j
1
​

​
−b
j
2
​

​


=0，那么我们就会得到这个不等式：

�
�
≥
(
�
�
�
1
+
�
�
1
)
−
(
�
�
�
2
+
�
�
2
)
�
�
1
−
�
�
2
a
i
​
≥
b
j
1
​

​
−b
j
2
​

​

(dp
j
1
​

​
+d
j
1
​

​
)−(dp
j
2
​

​
+d
j
2
​

​
)
​

如果
�
�
1
−
�
�
2

0
b
j
1
​

​
−b
j
2
​

​
=0，你可以认为上面那个值是
∞
∞。

这里我们令
�
(
�
)

�
�
,
�
(
�
)

�
�
�
+
�
�
X(i)=b
i
​
,Y(i)=dp
i
​
+d
i
​
，那么不等式变为：

�
�
≥
�
(
�
1
)
−
�
(
�
2
)
�
(
�
1
)
−
�
(
�
2
)
a
i
​
≥
X(j
1
​
)−X(j
2
​
)
Y(j
1
​
)−Y(j
2
​
)
​

将
(
�
(
�
)
,
�
(
�
)
)
(X(j),Y(j)) 作为
�
j 的对应点放入平面。如果
�
1
j
1
​
与
�
2
j
2
​
构成的直线斜率小于等于
�
�
a
i
​
（这里
�
1
,
�
2
j
1
​
,j
2
​
作为决策点出现），那么
�
2
j
2
​
优于
�
1
j
1
​
；否则
�
1
j
1
​
优于
�
2
j
2
​
。

假设
�
∈
[
�
−
�
,
�
−
�
]
j∈[i−x,i−y]，那么下图的点就是对应到平面上的散点：

我们把目光放到
�
,
�
,
�
A,B,C 三个点上，这里假设
�
,
�
A,B 构成的直线斜率是
�
1
k
1
​
，
�
,
�
B,C 构成的直线斜率是
�
2
k
2
​
，此处我们钦定
�
1

�
2
k
1
​

k
2
​
。

如果
�
2
<
�
1
≤
�
�
k
2
​
<k
1
​
≤a
i
​
，那么
�
C 是最优点
如果
�
2
≤
�
�
<
�
1
k
2
​
≤a
i
​
<k
1
​
，那么
�
C 是最优点
如果
�
�
<
�
2
<
�
1
a
i
​
<k
2
​
<k
1
​
，那么
�
A 是最优点
也就是说，
�
B 永远不会存为最优点，就要淘汰掉（太馋人，哦不太残忍了）。

同样的道理，这里看似有这么多点，但实则只有下凸包上的点会用到：

又因为下凸包的斜率是单调递增的，如果
�
j 前面的斜率都是小于等于
�
�
a
i
​
，后面的斜率都是

�
�

a
i
​
，那么
�
j 就是当前的最优决策点。

那不对呀！上凸包怎么能被忽略呢？！

所以如果上面不等式是
�
�
≤
�
(
�
1
)
−
�
(
�
2
)
�
(
�
1
)
−
�
(
�
2
)
a
i
​
≤
X(j
1
​
)−X(j
2
​
)
Y(j
1
​
)−Y(j
2
​
)
​
的话，那么决策点就在上凸包上啦！

推导二
TA 回来了：

�
�
�

min
⁡
�

�
−
�
�
−
�
(
�
�
�
+
�
�
×
�
�
+
�
�
+
�
�
+
�
)
dp
i
​

j=i−x
min
i−y
​
(dp
j
​
+a
i
​
×b
j
​
+c
i
​
+d
j
​
+M)
先假装看不见
min
⁡
min：

�
�
�

�
�
�
+
�
�
×
�
�
+
�
�
+
�
�
+
�
dp
i
​
=dp
j
​
+a
i
​
×b
j
​
+c
i
​
+d
j
​
+M
进一步：

�
�
�
+
�
�

−
�
�
×
�
�
+
�
�
�
−
�
�
−
�
dp
j
​
+d
j
​
=−a
i
​
×b
j
​
+dp
i
​
−c
i
​
−m
令
�

�
�
�
+
�
�
,
�

−
�
�
,
�

�
�
,
�

�
�
�
−
�
�
−
�
y=dp
j
​
+d
j
​
,k=−a
i
​
,x=b
j
​
,b=dp
i
​
−c
i
​
−m，那么上式就变成了
�

�
�
+
�
y=kx+b，此时最小化
�
�
�
dp
i
​
就相当于最小化
�
b。

怎样移向呢？看法则：

�
,
�
x,y 与
�
i 无关
�
,
�
k,b 与
�
j 无关
�
b 中要有我们要求的
�
�
�
dp
i
​

我们把每一个
�
,
�
x,y 当成一个点对应到平面上，这就是我们的决策点。接着我们用
�

−
�
[
�
]
k=−a[i] 的直线去对准每一个点（如图），看看哪条直线的截距（也就是
�
b）最小就好了。

你看，最优决策点的位置不变，说明最优决策点还是在下凸包的斜率单峰处。

当然，最大化
�
b 就是上凸包。

总结
其实它们本质是相同的，可以相辅相成地来理解。

接下来，明白了最优决策点在什么位置，那该怎么快速地找最优决策点呢？

如果状态转移决策具有决策单调性（放在刚才的例子里就是
∀
�

�
,
�
�

�
�
∀i>j,a
i
​

a
j
​
，即二次项系数
�
�
a
i
​
单调递增，此时随着和斜率比较的
�
�
a
i
​
的不断增加，由于下凸包上的点单调递增，
�
�
a
i
​
卡到下凸包上的点一定越来越靠后），则可以用单调队列维护凸包上的点（单调队列返厂啦！）。
如果不具有决策单调性，则根据凸包的单调性二分即可。
例题讲解
P3195 [HNOI2008] 玩具装箱
题目分析
状态设计：定义
�
�
�
dp
i
​
表示对于前
�
i 个玩具，若
�
i 作为所属分组的最后一个玩具，求总的最小花费。
转移方程：
�
�
�
=
min
⁡
�
=
1
�
−
1
{
�
�
�

(
�
−
(
�
+
1
)
+
(
∑
�

�
�
�
�
)
−
�
)
2
}
dp
i
​

j=1
min
i−1
​
{dp
j
​
+(i−(j+1)+(
k=j
∑
i
​
C
k
​
)−L)
2
}
设
�
�

∑
�

1
�
�
�
,
�

�
+
1
S
i
​
=∑
j=1
i
​
C
j
​
,M=L+1，则转移方程变为：

�
�
�

min
⁡
�

1
�
−
1
{
�
�
�
+
(
�
�
−
�
�
−
�
)
2
}
dp
i
​

j=1
min
i−1
​
{dp
j
​
+(S
i
​
−S
j
​
−M)
2
}
拆开：

�
�
�

min
⁡
�

1
�
−
1
{
�
�
�
+
�
�
2
+
�
�
2
+
�
2
−
2
�
�
�
�
−
2
�
�
�
+
2
�
�
�
}
dp
i
​

j=1
min
i−1
​
{dp
j
​
+S
i
2
​
+S
j
2
​
+M
2
−2S
i
​
S
j
​
−2S
i
​
M+2S
j
​
M}
发现了
2
�
�
�
�
2S
i
​
S
j
​
，因此斜率优化必定了。

状态初始化：
�
�
0

0
dp
0
​
=0。
答案就是
�
�
�
dp
n
​
。

如果当前状态为
�
�
�
dp
i
​
，若存在决策点
�
1
,
�
2
(
�
1
<
�
2
)
j
1
​
,j
2
​
(j
1
​
<j
2
​
)，且
�
2
j
2
​
优于
�
1
j
1
​
，则：

�
�
�
2
+
�
�
2
+
�
�
2
2
+
�
2
−
2
�
�
�
�
2
−
2
�
�
�
+
2
�
�
2
�
≤
�
�
�
1
+
�
�
2
+
�
�
1
2
+
�
2
−
2
�
�
�
�
1
−
2
�
�
�
+
2
�
�
1
�
�
�
�
2
+
�
�
2
2
−
2
�
�
�
�
2
+
2
�
�
2
�
≤
�
�
�
1
+
�
�
1
2
−
2
�
�
�
�
1
+
2
�
�
1
�
2
�
�
(
�
�
1
−
�
�
2
)
≥
(
�
�
�
1
+
�
�
1
2
+
2
�
�
1
�
)
−
(
�
�
�
2
+
�
�
2
2
+
2
�
�
2
�
)
∵
�
�
≥
1
,

�
1
≠
�
2
∴
�
�
1
−
�
�
2
≠
0
2
�
�
≥
(
�
�
�
1
+
�
�
1
2
+
2
�
�
1
�
)
−
(
�
�
�
2
+
�
�
2
2
+
2
�
�
2
�
)
�
�
1
−
�
�
2
dp
j
2
​

​
+S
i
2
​
+S
j
2
​

2
​
+M
2
−2S
i
​
S
j
2
​

​
−2S
i
​
M+2S
j
2
​

​
M
dp
j
2
​

​
+S
j
2
​

2
​
−2S
i
​
S
j
2
​

​
+2S
j
2
​

​
M
2S
i
​
(S
j
1
​

​
−S
j
2
​

​
)
2S
i
​

​

≤dp
j
1
​

​
+S
i
2
​
+S
j
1
​

2
​
+M
2
−2S
i
​
S
j
1
​

​
−2S
i
​
M+2S
j
1
​

​
M
≤dp
j
1
​

​
+S
j
1
​

2
​
−2S
i
​
S
j
1
​

​
+2S
j
1
​

​
M
≥(dp
j
1
​

​
+S
j
1
​

2
​
+2S
j
1
​

​
M)−(dp
j
2
​

​
+S
j
2
​

2
​
+2S
j
2
​

​
M)
∵C
i
​
≥1, j
1
​


=j
2
​

∴S
j
1
​

​
−S
j
2
​

​


=0
≥
S
j
1
​

​
−S
j
2
​

​

(dp
j
1
​

​
+S
j
1
​

2
​
+2S
j
1
​

​
M)−(dp
j
2
​

​
+S
j
2
​

2
​
+2S
j
2
​

​
M)
​

​

令
�
(
�
)

�
�
,

�
(
�
)

�
�
[
�
]
+
�
�
2
+
2
�
�
�
X(j)=S
j
​
, Y(j)=dp[j]+S
j
2
​
+2S
j
​
M，得：

2
�
�
≥
�
(
�
1
)
−
�
(
�
2
)
�
(
�
1
)
−
�
(
�
2
)
2S
i
​
≥
X(j
1
​
)−X(j
2
​
)
Y(j
1
​
)−Y(j
2
​
)
​

满足此条件时有
�
2
j
2
​
优于
�
1
j
1
​
，则根据原理处的推导，只需要维护
�
∈
[
1
,
�
−
1
]
j∈[1,i−1] 对应的点集
(
�
(
�
)
,
�
(
�
)
)
(X(j),Y(j)) 的下凸包即可。

又由于
�
�
S
i
​
单调递增，所以状态转移具有决策单调性，可以用单调队列维护，即不是
�
i 的最优决策点的点不会再是
�
+
1
i+1 的最优决策点。

注意：

单调队列中维护凸包上的点对应的
�
j。
维护的点不应存在三点共线，而应当只维护两端点。
单调队列中应保证至少有两个点再求斜率，deque 难以实现且常数大，建议使用手写队列。
维护凸包比较斜率时建议不要使用除法，容易被卡精度，交叉相乘是更好的选择。同时，
�
0
≥
�
�
0
a
​
≥
c
b
​
交叉相乘后恒成立，这难道不正是我们一直在找的
�
0

∞
0
a
​
=∞ 的可行实现方案吗？
代码实现
cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e4 + 10;
int n, L, c[N];
int dp[N], s[N], a[N], b[N];
int q[N], h = 1, t = 1;
int X(int p) { return b[p]; }
int Y(int p) { return dp[p] + b[p] * b[p]; }
double slope(int a, int b) {
if (X(a) == X(b)) {
if (Y(a) == Y(b)) return 0; // 斜率无法比较
if (Y(a) > Y(b)) return -1e18; // 斜率为负无穷
else return 1e18; // 斜率为正无穷
}
return (Y(a) - Y(b)) * 1.00 / (X(a) - X(b));
}

signed main() {
scanf(“%lld%lld”, &n, &L);
for (int i = 1; i <= n; i++) scanf(“%lld”, &c[i]), s[i] = s[i - 1] + c[i];
for (int i = 0; i <= n; i++) a[i] = s[i] + i, b[i] = s[i] + i + L + 1;
q[1] = 0;
for (int i = 1; i <= n; i++) {
// 由于凸包的斜率一定单调递增，于是把队头斜率小于 2 * a[i] 的点删除
while (h < t && slope(q[h], q[h + 1]) <= 2 * a[i]) h++;
int j = q[h];
dp[i] = dp[j] + (a[i] - b[j]) * (a[i] - b[j]); // 状态转移方程
// 把队尾的斜率小于当前点的坐标删除，放入当前点
while (h < t && slope(q[t - 1], q[t]) >= slope(q[t], i)) t–;
q[++t] = i;
}
printf(“%lld\n”, dp[n]);
return 0;
}
P2365 [IOI 2002] 任务安排
题目分析
状态设计：用
�
�
�
,
�
dp
i,j
​
表示前
�
i 个任务分成
�
j 组，
�
i 为第
�
j 组最后一个任务，完成所有任务所需时间的最小值。
转移方程：
�
�
�
,
�

min
⁡
�
−
1
≤
�
<
�
�
�
�
,
�
−
1
+
∑
�

�
+
1
�
�
�
�
�
×
�
�
+
�

min
⁡
�
−
1
≤
�
<
�
�
�
�
,
�
−
1
+
�
�
�
�
×
∑
�

�
+
1
�
�
�
+
�
dp
i,j
​

​

=
j−1≤k<i
min
​
dp
k,j−1
​
+
p=k+1
∑
i
​
tim
j
​
×f
k
​
+s

j−1≤k<i
min
​
dp
k,j−1
​
+tim
j
​
×
p=k+1
∑
i
​
f
k
​
+s
​

优化一下，假设
�
�

∑
�

1
�
�
�
�
�
,
�
�

∑
�

1
�
�
�
T
i
​
=∑
j=1
i
​
tim
j
​
,F
i
​
=∑
j=1
i
​
f
j
​
。
则上式变为：

�
�
�
,
�

min
⁡
�
−
1
≤
�
<
�
�
�
�
,
�
−
1
+
�
�
�
�
×
(
�
�
−
�
�
)
dp
i,j
​

j−1≤k<i
min
​
dp
k,j−1
​
+tim
j
​
×(F
i
​
−F
k
​
)