社区讨论
这题为啥不能用 double 判斜率啊
CF311BCats Transport参与者 6已保存回复 9
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @loc7skwh
- 此快照首次捕获于
- 2023/10/30 09:21 2 年前
- 此快照最后确认于
- 2023/11/04 18:53 2 年前
之前写的是这样的:
CPPfor(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;
}
}
可是这不是等价的吗,以前这么写没出过问题啊 ,难道是精度问题?





回复
共 9 条回复,欢迎继续交流。
正在加载回复...