社区讨论

这题为啥不能用 double 判斜率啊

CF311BCats Transport参与者 6已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@loc7skwh
此快照首次捕获于
2023/10/30 09:21
2 年前
此快照最后确认于
2023/11/04 18:53
2 年前
查看原帖
之前写的是这样的:
CPP
for(re int i=1;i<=p;i++){
        head=1;tail=0;q[++tail]=0;
        for(re int j=1;j<=m;j++){
            while(head<tail&&slope(q[head],q[head+1])<K(j))head++;
            f[i][j]=Y(q[head])-K(j)*q[head]+j*A[j]-sum[j];
            while(head<tail&&slope(q[tail-1],q[tail])<slope(q[tail-1],j))tail--;
            q[++tail]=j;
        }
    }
改成这样就 A 了:
CPP
 for(re int i=1;i<=p;i++){
        head=1;tail=0;q[++tail]=0;
        for(re int j=1;j<=m;j++){
            while(head<tail&&Y(q[head])-Y(q[head+1])>K(j)*(q[head]-q[head+1]))head++;
            f[i][j]=Y(q[head])+A[j]*(j-q[head])-sum[j];
            while(head<tail&&(Y(j)-Y(q[tail-1]))*(q[tail]-q[tail-1])<(Y(q[tail])-Y(q[tail-1]))*(j-q[tail-1]))tail--;
            q[++tail]=j;
        }
    }
可是这不是等价的吗,以前这么写没出过问题啊 ,难道是精度问题?/kk/kk/kk

回复

9 条回复,欢迎继续交流。

正在加载回复...