「ZJOI2007」仓库建设
题意：有 \(n\) 个工厂，由高到底分布在一座山上，工厂 \(1\) 在山顶，工厂 \(n\) 在山脚，第 \(i\) 个工厂有 \(p_i\) 件产品，距离工厂 \(1\) 的距离为 \(x_i\)，在第 \(i\) 个工厂位置建立仓库的费用是 \(c_i\)，对于没有建立仓库的工厂，要将产品运往山下的仓库（即只能运往编号更大的工厂的仓库），求最小花费（运输费用+建立费用）
设 \(dp_i\) 表示在 \(i\) 建立仓库的最小花费
可得 \(dp_i=min_{0 \le j \le i-1}(dp_j + c_i + \sum_{l=j+1}^{i-1} (x_i - x_l) \times p_l)\)
但是发现并不好维护，时间复杂度为 \(O(n^3)\)，于是可以转化一下
\(dp_i=min_{0 \le j \le i-1}(dp_j + c_i + \sum_{l=j+1}^{i-1} x_i \times p_l - \sum_{l=j+1}^{i-1} x_l \times p_l)\)
那么记 \(s1_i=\sum_{j=1}^{i} p_i \times x_i\)，\(s2_i=\sum_{j=1}^{i} p_i\)
于是 \(dp_i=min_{0 \le j \le i-1}(dp_j + c_i + x_i \times (s2_{i-1}-s2_j) - s1_{i-1} + s1_j)\)
此时时间复杂度为 \(O(n^2)\)
#include<bits/stdc++.h>
using namespace std;
int n,dp[1000001],x[1000001],p[1000001],c[1000001],s1[1000001],s2[1000001];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&p[i],&c[i]),s1[i]=s1[i-1]+x[i]*p[i],s2[i]=s2[i-1]+p[i];
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++) for(int j=0;j<i;j++) dp[i]=min(dp[i],dp[j]+c[i]+x[i]*(s2[i-1]-s2[j])-s1[i-1]+s1[j]);
printf("%d",dp[n]);
return 0;
}
此时直接斜率优化
同任务安排一样，将 \(min\) 去掉，把关于 \(j\) 的值 \(dp_j + s1_j\) 看作平面坐标直角系的 \(y\) 和 \(s2_j\) 看作 \(x\)，其余部分看作常数
\(dp_j + s1_j=x_i \times s2_j + dp_i - c_i - x_i \times s2_{i-2} + s1_{i-1}\)
然后直接单调队列维护下凸包，这里可以不用二分，因为并没有负数，时间复杂度 \(O(n)\)
#include<bits/stdc++.h>
using namespace std;
int n,head=1,tail=1;
long long dp[1000001],x[1000001],p[1000001],c[1000001],s1[1000001],s2[1000001],q[1000001];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&x[i],&p[i],&c[i]),s1[i]=s1[i-1]+x[i]*p[i],s2[i]=s2[i-1]+p[i];
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
while(head<tail&&(dp[q[head+1]]+s1[q[head+1]]-dp[q[head]]-s1[q[head]])<=x[i]*(s2[q[head+1]]-s2[q[head]])) head++;
dp[i]=dp[q[head]]+c[i]+x[i]*(s2[i-1]-s2[q[head]])-s1[i-1]+s1[q[head]];
while(head<tail&&(dp[q[tail]]+s1[q[tail]]-dp[q[tail-1]]-s1[q[tail-1]])*(s2[i]-s2[q[tail]])>=(dp[i]+s1[i]-dp[q[tail]]-s1[q[tail]])*(s2[q[tail]]-s2[q[tail-1]])) tail--;
q[++tail]=i;
}
printf("%lld",dp[n]);
return 0;
}