2 条题解

  • 0
    @ 2025-10-8 16:58:48

    /* dp[i]=min(dp[i], dp[j]+st[i](sf[i]-sf[j])+s(sf[n]-sf[j]));

    dp[i]=dp[j]+st[i](sf[i]-sf[j])+s(sf[n]-sf[j]));

    dp[i]-st[i]sf[i]-ssf[n]= dp[j]-s*sf[j]- st[i]sf[j] dp[j]-ssf[j] =st[i]sf[j] + dp[i]-st[i]sf[i]-ssf[n] yj=dp[j]-ssf[j] xj=sf[j] k=st[i] b=dp[i]-st[i]sf[i]-ssf[n]

    */

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N=310000;
    LL dp[N], f[N], t[N], st[N], sf[N], s; int q[N];
    double X(int j){ return 1.0*sf[j];}
    double Y(int j){ return 1.0*(dp[j]-s*sf[j]);}
    double K(int j1, int j2){return (X(j2)==X(j1))?1e18*( Y(j2)-Y(j1) ) : ( Y(j2)-Y(j1) ) / ( X(j2)-X(j1) )  ;}
    int main()
    {
    	//freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); 
        int n; scanf("%d%lld", &n, &s);
        st[0]=0; sf[0]=0; 
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld", &t[i], &f[i]);
            st[i]=st[i-1]+t[i];
            sf[i]=sf[i-1]+f[i];
        }
        int l=1, r=1; q[1]=0; dp[0]=0;
        for(int i=1;i<=n;i++)
        {
            while(l<r && K(q[l], q[l+1]) <= st[i] ) l++;
            dp[i]=dp[q[l]] + st[i]*(sf[i]-sf[q[l]]) + s*(sf[n]-sf[q[l]]);
            while( l<r && K(q[r-1], q[r] ) >= K(q[r], i) ) r--;
            q[++r]=i;    
        }
        printf("%lld\n", dp[n]);
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:58:32
      /*
      dp[i]=min(dp[i],dp[j]+st[i]*(sf[i]-sf[j])+s*(sf[n]-sf[j]));
       
      dp[i]=dp[j]+st[i]*(sf[i]-sf[j])+s*(sf[n]-sf[j]));
       
      dp[i]-st[i]*sf[i]-s*sf[n]=  dp[j]-s*sf[j]- st[i]*sf[j]
      dp[j]-s*sf[j] =st[i]*sf[j] + dp[i]-st[i]*sf[i]-s*sf[n]
      yj=dp[j]-s*sf[j]
      xj=sf[j]
      k=st[i]
      b=dp[i]-st[i]*sf[i]-s*sf[n]
       
      */
      #include<bits/stdc++.h>
      using namespace std;
      typedef long long LL;
      const int N=310000;
      LL dp[N],f[N],t[N],st[N],sf[N],s;int q[N];
      double X(int j){ return 1.0*sf[j];}
      double Y(int j){ return 1.0*(dp[j]-s*sf[j]);}
      double K(int j1,int j2){return (X(j2)==X(j1))?1e18*( Y(j2)-Y(j1) ) :( Y(j2)-Y(j1) ) / ( X(j2)-X(j1) )  ;}
      int main()
      {
      	//freopen("a.in","r",stdin);freopen("a.out","w",stdout); 
          int n;scanf("%d%lld",&n,&s);
          st[0]=0;sf[0]=0; 
          for(int i=1;i<=n;i++)
          {
              scanf("%lld%lld",&t[i],&f[i]);
              st[i]=st[i-1]+t[i];
              sf[i]=sf[i-1]+f[i];
          }
          int l=1,r=1;q[1]=0;dp[0]=0;
          for(int i=1;i<=n;i++)
          {
              while(l<r && K(q[l],q[l+1])<=st[i] ) l++;
              dp[i]=dp[q[l]]+st[i]*(sf[i]-sf[q[l]])+s*(sf[n]-sf[q[l]]);
              while( l<r && K(q[r-1],q[r] ) >= K(q[r],i) ) r--;
              q[++r]=i;    
          }
          printf("%lld\n",dp[n]);
          return 0;
      }
      • 1

      信息

      ID
      1809
      时间
      1000ms
      内存
      512MiB
      难度
      5
      标签
      递交数
      45
      已通过
      17
      上传者