定义 dpi 是把前 i 个工厂料理完,在 i 处建了一个仓库的最小花费。然后我推出了这样一个柿子:
dpi=minj<i{dpj+ci+(sumpi−sumpj)×xi−(sumpxi−sumpxj)}
其中 sumpi 表示 pi 的前缀和,sumpxi 表示 pi×xi 的前缀和。
然后我们有点的坐标 (sumpi,dpi−sumpxi) 斜率:xi。排序后能够保证斜率是递增的。然后写挂了,WA11分,不知道为什么,求助。
#include<bits/stdc++.h>
using namespace std;
struct node{
long long xt,pt,ct;
friend bool operator<(node a,node b){
return a.xt<b.xt;
}
}cts[1000005];
long long n,x[1000005],p[1000005],c[1000005],sp[1000005];
long long spx[1000005],dp[1000005],deq[1000005],s=1,t=1;
long double slope(int u,int v){
if(sp[u]==sp[v])
return 1e18;
return ((long double)dp[u]-spx[u]-dp[v]+spx[v])/((long double)sp[u]-sp[v]);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>cts[i].xt>>cts[i].pt>>cts[i].ct;
sort(cts+1,cts+n+1);
for(int i=1;i<=n;i++){
x[i]=cts[i].xt;
p[i]=cts[i].pt;
c[i]=cts[i].ct;
sp[i]=sp[i-1]+p[i];
spx[i]=spx[i-1]+p[i]*x[i];
}
for(int i=1;i<=n;i++){
while(s<t&&slope(deq[s],deq[s+1])<x[i])
s++;
dp[i]=dp[deq[s]]+c[i]+(sp[i]-sp[deq[s]])*x[i]-(spx[i]-spx[deq[s]]);
while(s<t&&slope(deq[t-1],deq[t])>slope(deq[t],i))
t--;
deq[++t]=i;
}
cout<<dp[n];
}