关于斜率优化的取等问题
查看原帖
关于斜率优化的取等问题
234783
conprour楼主2021/10/29 15:33

RT,单调栈弹出栈顶元素的时候,斜率相等的时候为什么要弹出,不然会错。斜率相等的时候,截距也是一样的,弹不弹出应该都一样吧?

75pts

for(int i=1;i<=n;i++)
{
	int j=find(sumT[i]);
	dp[i]=Y(j)+sumT[i]*(sumC[i]-sumC[j])+sumC[n]*s;
	while(l<r&&(X(i)-X(q[r-1]))*(Y(q[r])-Y(q[r-1]))>=(X(q[r])-X(q[r-1]))*(Y(i)-Y(q[r-1]))) r--;
	q[++r]=i; 
}

AC

	for(int i=1;i<=n;i++)
	{
		int j=find(sumT[i]);
		dp[i]=Y(j)+sumT[i]*(sumC[i]-sumC[j])+sumC[n]*s;
		while(l<r&&(X(i)-X(q[r-1]))*(Y(q[r])-Y(q[r-1]))>=(X(q[r])-X(q[r-1]))*(Y(i)-Y(q[r-1]))) r--;
		q[++r]=i; 
	}
2021/10/29 15:33
加载中...