2 条题解

  • 0
    @ 2025-10-8 16:49:38
    /*
    f[i]=f[j]+a[j+1].y*a[i].x;
    f[j]=-a[j+1].y*a[i].x + f[i];
    yj=f[j]
    xj=-a[j+1].y 
    k=a[i].x
    b=f[i]
    */ 
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N=51100;
    struct node{ LL x,y;}a[N];
    bool cmp(node n1,node n2){if( n1.x!=n2.x) return n1.x<n2.x;else return n1.y<n2.y;}
    LL  f[N];
    int q[N];
    double X(int j){ return -1.0*a[j+1].y;}
    double Y(int j){ return 1.0*f[j];} 
    double slop(int j1,int j2){return (X(j2)==X(j1))?1e18*( Y(j2)-Y(j1) ):( Y(j2)-Y(j1) )/( X(j2)-X(j1) );}
    int main()
    {
        int n;scanf("%lld%lld", &n);
        for(int i=1;i<=n;i++)scanf("%lld%lld", &a[i].x, &a[i].y);
        sort(a+1,a+n+1,cmp);
        int tn=1;
        for(int i=2;i<=n;i++)
        {
            while(tn>0 && a[tn].y<=a[i].y)tn--;
            a[++tn]=a[i];
        }
        int l=1,r=1;q[1]=0;n=tn;
        for(int i=1;i<=n;i++)
        {
            while(l<r && slop(q[l],q[l+1])<a[i].x)l++;
            f[i]= f[q[l]]+ a[q[l]+1].y*a[i].x ;
            while(l<r && slop(q[r-1],q[r])>slop(q[r],i) )r--;
            q[++r]=i;
        }
        printf("%lld\n",f[n]);
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:49:26
      /*
      f[i]=f[j]+a[j+1].y*a[i].x;
      f[j]=-a[j+1].y*a[i].x + f[i];
      yj=f[j]
      xj=-a[j+1].y 
      k=a[i].x
      b=f[i]
      */ 
      #include<bits/stdc++.h>
      using namespace std;
      typedef long long LL;
      const int N=51100;
      struct node{ LL x,y;}a[N];
      bool cmp(node n1,node n2){if( n1.x!=n2.x) return n1.x<n2.x;else return n1.y<n2.y;}
      LL  f[N];
      int q[N];
      double X(int j){ return -1.0*a[j+1].y;}
      double Y(int j){ return 1.0*f[j];} 
      double slop(int j1,int j2){return (X(j2)==X(j1))?1e18*( Y(j2)-Y(j1) ):( Y(j2)-Y(j1) )/( X(j2)-X(j1) )  ;}
      int main()
      {
          int n;scanf("%d",&n);
          for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].x,&a[i].y);
          sort(a+1,a+n+1,cmp);//每块长方形排序:先考虑X从小到大,如果X相等再考虑Y从小到大 
          int tn=1;
          for(int i=2;i<=n;i++)//经常这样优化数据 
          {
              while(tn>0 && a[tn].y<=a[i].y)tn--;
              a[++tn]=a[i];
          }
          int l=1,r=1;q[1]=0;n=tn;
          for(int i=1;i<=n;i++)
          {
              while(l<r && slop(q[l],q[l+1])<a[i].x)l++;
              f[i]= f[q[l]]+ a[q[l]+1].y*a[i].x ;
              while(l<r && slop(q[r-1],q[r])>slop(q[r],i) )r--;
              q[++r]=i;
          }
          printf("%lld\n",f[n]);
          return 0;
      }
      • 1

      *【斜率优化】土地征用 [USACO08MAR] Land Acquisition G

      信息

      ID
      333
      时间
      300ms
      内存
      128MiB
      难度
      6
      标签
      递交数
      135
      已通过
      39
      上传者