2 条题解
-
0
/* 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
/* 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
信息
- ID
- 333
- 时间
- 300ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 135
- 已通过
- 39
- 上传者