1 条题解

  • 1
    @ 2021-8-8 1:34:48

    C++ :

    #include <bits/stdc++.h>
    using namespace std;
    long long f[300010],sumt[300010],sumc[300010];
    int q[300010],n,s;
    int main(){
       cin>>n>>s;
        for(int i=1;i<=n;i++)
        {
          int t,c;cin>>t>>c;
          sumt[i]=sumt[i-1]+t;
          sumc[i]=sumc[i-1]+c;
          }
       memset(f,0x3f,sizeof(f));
        int l=1,r=1;
       f[0]=0,   q[l]=0;
        for(int i=1;i<=n;i++)
        {
          while(l < r && (f[q[l+1]]-f[q[l]]) <= (s+sumt[i])*(sumc[q[l+1]] - sumc[q[l]])) l++;
          f[i]=f[q[l]] - (s+sumt[i])*sumc[q[l]] + sumt[i]*sumc[i] + s*sumc[n];
          while(l < r && (f[q[r]] - f[q[r-1]]) * (sumc[i] -sumc[q[r]]) >= (f[i]-f[q[r]]) * (sumc[q[r]] - sumc[q[r-1]])) r--;
          q[++r] =i;
          }
       cout<<f[n]<<endl;
        return 0;
    }
    
    • 1

    信息

    ID
    212
    时间
    1000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    19
    已通过
    12
    上传者