这道题因为斜率可能不是一直递增, 所以要用二分来维护
- #include<iostream>
- #include<algorithm>
- #include<cstdio>
- #include<vector>
- using namespace std;
- typedef long long ll;
- const int N=3e5+10;
- int q[N];
- ll f[N];
- ll st[N],sc[N];
- int getup(int i,int j){
- return f[i]-f[j];
- }
- int getdown(int i,int j){
- return sc[i]-sc[j];
- }
- int main(){
- int n,s;
- cin>>n>>s;
- int i;
- for(i=1;i<=n;i++){
- scanf("%lld%lld",&st[i],&sc[i]);
- st[i]+=st[i-1];
- sc[i]+=sc[i-1];
- }
- int hh=0;
- int tt=0;
- q[0]=0;
- for(i=1;i<=n;i++){
- int l=hh,r=tt;
- while(l<r){
- int mid=l + r>>1;
- if((f[q[mid + 1]] - f[q[mid]])> (st[i] + s) * (sc[q[mid + 1]] - sc[q[mid]]))
- r = mid;
- else l = mid + 1;
- }
- f[i] = f[q[l]] - (st[i] + s) * sc[q[l]] + sc[i] * st[i] + s * sc[n];
- while (hh <tt && (f[q[tt]] - f[q[tt - 1]]) * (sc[i] - sc[q[tt]])>= (f[i] - f[q[tt]]) * (sc[q[tt]] - sc[q[tt - 1]]))
- tt -- ;
- q[++tt]=i;
- }
- cout<<f[n]<<endl;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3474567.html