朴素 DP
记 $\textit{dp}_i$ 表示第 $i$ 个工厂必须建仓库，第 $1\sim i$ 个工厂的总花费。
则有：
\[\begin{aligned} \textit{dp}_i&=c_i+\min_{j=0}^{i-1}\left(\textit{dp}_j+\sum_{k=j+1}^i(x_i-x_k)p_k\right)\\ &=c_i+\min_{j=0}^{i-1}\left(\textit{dp}_j+x_i\sum_{k=j+1}^ip_k-\sum_{k=j+1}^{i-1}x_kp_k\right) \end{aligned}\]记：
\[\begin{aligned} \textit{prep}_i&=\sum_{j=1}^ip_j\\ \textit{prexp}_i&=\sum_{j=1}^ix_jp_j \end{aligned}\]则有：
\[\begin{aligned} \textit{dp}_i&=c_i+\min_{j=0}^{i-1}\left(\textit{dp}_j+\sum_{k=j+1}^i(x_i-x_k)p_k\right)\\ &=c_i+\min_{j=0}^{i-1}\left(\textit{dp}_j+x_i\left(\textit{prep}_i-\textit{prep}_j\right)-\left(\textit{prexp}_i-\textit{prexp}_j\right)\right)\\ &=c_i+x_i\textit{prep}_i-\textit{prexp}_i+\min_{j=0}^{i-1}\left(\textit{dp}_j-x_i\textit{prep}_j+\textit{prexp}_j\right) \end{aligned}\]时间复杂度：$\mathcal O\left(n^2\right)$。
斜率优化 DP
发现递推式中关于 $j$ 的部分 $\textit{dp}_j-x_i\textit{prep}_j+\textit{prexp}_j$ 仅有一项与 $i$ 相关，考虑斜率优化 DP。
设决策点 $j_1<j_2$，钦定 $j_1$ 优于 $j_2$，有：
\[\begin{aligned} \textit{dp}_{j_1}-x_i\textit{prep}_{j_1}+\textit{prexp}_{j_1}&\leq \textit{dp}_{j_2}-x_i\textit{prep}_{j_2}+\textit{prexp}_{j_2}\\ x_i(\textit{prep}_{j_2}-\textit{prep}_{j_1})&\leq\left(\textit{dp}_{j_2}+\textit{prexp}_{j_2}\right)-\left(\textit{dp}_{j_1}+\textit{prexp}_{j_1}\right)\\ x_i&\leq\dfrac{\left(\textit{dp}_{j_2}+\textit{prexp}_{j_2}\right)-\left(\textit{dp}_{j_1}+\textit{prexp}_{j_1}\right)}{\textit{prep}_{j_2}-\textit{prep}_{j_1}}\\ x_i&\leq\dfrac{\left(\textit{dp}_{j_1}+\textit{prexp}_{j_1}\right)-\left(\textit{dp}_{j_2}+\textit{prexp}_{j_2}\right)}{\textit{prep}_{j_1}-\textit{prep}_{j_2}}\\ \end{aligned}\]因此可以有决策点 $A_j\left(\textit{prep}_j,\textit{dp}_j+\textit{prexp}_j\right)$。单调队列维护下凸壳即可。
时间复杂度 $\mathcal O(n)$。
AC 代码
注意 double 精度问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=1000000;
constexpr const ll inf=0x3f3f3f3f3f3f3f3f;
constexpr const double eps=1e-8;
int n,x[N+1],p[N+1],c[N+1];
ll prep[N+1],prexp[N+1],dp[N+1];
struct slopeDP{
struct node{
ll x,y;
int id;
}q[N+1];
int front,rear;
slopeDP(){
front=1;rear=0;
}
double slope(node i,node j){
return 1.0*(i.y-j.y)/(i.x-j.x);
}
bool check(node a,node b,node c,node d){
return (a.y-b.y)*(c.x-d.x) < (c.y-d.y)*(a.x-b.x);
}
void push(int id){
node x={prep[id],dp[id]+prexp[id],id};
//slope(q[rear],x)<slope(q[rear-1],q[rear])
while(front+1<=rear && check(q[rear],x,q[rear-1],q[rear])){
rear--;
}
q[++rear]=x;
}
int query(int x){
while(front+1<=rear && slope(q[front],q[front+1])<x){
front++;
}
return q[front].id;
}
}t;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i]>>p[i]>>c[i];
prep[i]=prep[i-1]+p[i];
prexp[i]=prexp[i-1]+1ll*x[i]*p[i];
}
t.push(0);
for(int i=1;i<=n;i++){
int j=t.query(x[i]);
dp[i]=c[i]+1ll*x[i]*prep[i]-prexp[i]+dp[j]-x[i]*prep[j]+prexp[j];
if(!p[i]){
dp[i]=min(dp[i],dp[i-1]);
}
t.push(i);
}
cout<<dp[n]<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
/*
3
0 5 10
5 3 100
9 6 10
32
*/
