Sample Output
153
思路：注意是只有一台机器，所以时间是累加的，那么影响到[j,N]。所以列出方程： f[i]=min(): f[j]+(sum2[N]-sum2[j])*(sum1[i]-sum1[j]+M)
直接dp复杂度是O(N^2)，使用效率优化：
//b=y-kx+c; --> f[i]=(-sum1[i]*sum2[j])+(f[j]+sum1[j]*sum2[j]-sum*sum1[j]-M*sum2[j])+(M*sum+sum*sum1[j]);
其中k之和i有关，y之和j有关，b就是f[i]，c是常数：k=sum1[i]，y=f[j]-sum2[N]*sum1[j]+sum2[j]*sum1[j]-sum2[j]*M;
可以看到我们需要维护一个斜率上升的凸包，由于K=sum1[i]没有说递增，所以我们不能弹出栈顶，求的时候用二分求得凸包极值。
注意：1，二分的时候，二分区间[0,top]，0代表的是，从头到尾都选，不能忽略。
2，每个新的i都要插入，插入当前i时，要维护斜率递增。
3，维护的图像的x和y分别的 y=kx+b的x和y，所以维护斜率，弹出栈尾比较斜率时，x是sum2[q[top]]，而不是q[top]；
//b=y-kx+c; --> f[i]=(-sum1[i]*sum2[j])+(f[j]+sum1[j]*sum2[j]-sum*sum1[j]-M*sum2[j])+(M*sum+sum*sum1[j]); #include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=1000010; ll sum1[maxn],sum2[maxn],f[maxn],M; int q[maxn],top,N; ll Y(int j){ return f[j]-sum2[N]*sum1[j]+sum2[j]*sum1[j]-sum2[j]*M; } ll getans(int i,int j){return f[j]+(sum2[N]-sum2[j])*(sum1[i]-sum1[j]+M);; } int main() { int i; scanf("%d%lld",&N,&M); for(i=1;i<=N;i++){ scanf("%lld%lld",&sum1[i],&sum2[i]); sum1[i]+=sum1[i-1]; sum2[i]+=sum2[i-1]; } for(int i=1;i<=N;i++){ int L=0,R=top,ans=top; while(L<=R){ int Mid=(L+R)>>1; if(getans(i,q[Mid])<=getans(i,q[Mid+1])) R=Mid-1,ans=Mid; else L=Mid+1; } f[i]=getans(i,q[ans]); while (top>0&& 1ll*(Y(q[top])-Y(q[top-1]))*(sum2[i]-sum2[q[top]])>=(Y(i)-Y(q[top]))*(sum2[q[top]]-sum2[q[top-1]]))
top--; q[++top]=i; //while语句里不是dx的时候不是下边之间减，是方程组的sum2来减。 } printf("%lld\n",f[N]); return 0; }
原文：https://www.cnblogs.com/hua-dong/p/9244749.html