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;
}