社区讨论

一个很有趣的问题

HHPXXZYY
P2900[USACO08MAR] Land Acquisition G参与者 3已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@mkp7026g
此快照首次捕获于
2026/01/22 16:31
2 个月前
此快照最后确认于
2026/01/22 23:56
2 个月前
查看原帖
斜率优化，为什么维护队尾和维护队头的顺序颠倒一下，连样例都过不去。
AC 的代码长这样：
CPP
	h=1;t=0;q[h]=0;
	for(int i=1;i<=n;i++){
		while (h<t&&Slope(q[t],q[t-1])>=Slope(q[t],i)) t--;
		q[++t]=i;
		
		while (h<t&&Slope(q[h],q[h+1])<=a[i].wid) h++;
		
		f[i]=f[q[h]-1]+1ll*a[i].wid*a[q[h]].len;
	}
如果交换一下队头和队尾的维护次序，即
CPP
	h=1;t=0;q[h]=0;
	for(int i=1;i<=n;i++){
		while (h<t&&Slope(q[h],q[h+1])<=a[i].wid) h++;
		f[i]=f[q[h]-1]+1ll*a[i].wid*a[q[h]].len;
  
  		while (h<t&&Slope(q[t],q[t-1])>=Slope(q[t],i)) t--;
		q[++t]=i;
	}
就连样例都是错的。

回复

共 2 条回复，欢迎继续交流。

正在加载回复...