基本和锯木厂一样。dp[i]表示在i建一个锯木厂的最优方案。则 dp[i]=min{dp[j]+c[i]-c[j]-sw[j]*(sd[i]-sd[j]}+w[i]。 具体见锯木厂。
#include <cstdio> #include <cstring> #define ll long long int const N=1000000+10; int d[N],w[N],n,q[N],h=0,t=0; ll sw[N],sd[N],c[N],dp[N]; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } inline double slope(int k1,int k2){ return (dp[k1]-dp[k2]+c[k2]-c[k1]+sw[k1]*sd[k1]-sw[k2]*sd[k2])*1.0/(1.0*(sw[k1]-sw[k2])); } int main(){ // freopen("a.in","r",stdin); n=read();//注意读入的是sd。。。 for(int i=1;i<=n;++i){ sd[i]=read();int x=read();w[i]=read(); sw[i]=sw[i-1]+x; } for(int i=1;i<=n;++i) d[i]=sd[i]-sd[i-1]; for(int i=1;i<=n;++i) c[i]=c[i-1]+sw[i-1]*d[i]; for(int i=1;i<=n;++i){ while(h<t&&slope(q[h],q[h+1])<sd[i]) ++h; dp[i]=dp[q[h]]+c[i]-c[q[h]]-sw[q[h]]*(sd[i]-sd[q[h]])+w[i]; while(h<t&&slope(q[t],i)<slope(q[t-1],q[t])) --t; q[++t]=i; } printf("%lld",dp[n]); return 0; }