自动搬运

查看原文

来自洛谷，原作者为

	Super_Cube AFO || 2020.09.20~2024.11.30 || 最后上线于 2024.12.31

搬运于2025-08-24 22:41:50，当前版本为作者最后更新于2023-12-05 10:29:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Solution

设 $dp_i$ 表示在 $i$ 号岛停下的最大 rp 值，定义 $\langle x\rangle$ 表示 $x$ 向 0 取整得到的值。

可以得到：$dp_i=\displaystyle\max_{j=1}^{i-1} \left\lbrace \left\langle \dfrac{dp_j}{2}\right\rangle + T_i \times T_j - F_j \right\rbrace$。

最后答案即为： $\displaystyle\max_{i=1}^n \{ dp_i\}$。

直接做复杂度过不去，考虑斜率优化，先将 $\max$ 去掉，改写此式为：$\left\langle \dfrac{dp_j}{2}\right\rangle - F_j = - T_i \times T_j + dp_i$。

以下内容是之前眼瞎的时候没看见数据范围里面保证了 $T_i$ 有序时候的做法，没兴趣可以略过。

现在的问题是式子中的斜率不单调的情况下连自变量也不单调，就不能像 P5785 那样用单调栈 + 二分进行维护凸包。

于是我们可以用 cdq 分治进行自变量的强制单调，这个时候你惊奇地发现斜率也随之单调了，所以在 cdq 内部处理时可以直接用单调队列维护凸包。

时间复杂度：$O(n\log n)$。

当然你可以在改写原 dp 式时像下面这样：$dp_i=T_j\times T_i+\left\langle \dfrac{dp_j}{2}\right\rangle-b_j$。

然后把它看成坐标系中的一次函数 / 一条直线，这题就变成李超线段树维护斜优 dp 了。

时间复杂度：$O(n\log V)$，其中 $V$ 为 $T$ 的值域大小。

这个做法代码比 cdq 短，跑得也比 cdq 快。

下面是本题保证了 $T_i$ 有序的做法。

我们对于上式进行换元：

$$\begin{cases} y=\left\langle \dfrac{dp_j}{2}\right\rangle - F_j\\ k=-T_i\\ x=T_j\\ b=dp_i\\ \end{cases} $$

这样就可以很清晰的看出上式是类似于一次函数的。

我们为了让 $dp_i$ 能够取得最大值，那么就要最大化截距 $b$，因为截距中只含有 $dp_i$，只要截距最大，$dp_i$ 肯定也是最大的。

所以我们要对于所有的决策点维护一个上凸包，这样我们拿斜率为 $k$ 的直线去切的时候截距 $b$ 才能最大化。

因为给定的 $T_i$ 是保证升序的，那么说明斜率 $k$ 与自变量 $x$ 都是单调的，就可以直接用单调队列维护凸包斜率。

时间复杂度： $O(n)$。

下面是这种方法的代码。

Code

#include<bits/stdc++.h>
#define X(i) (a[i])
#define Y(i) (dp[i]/2-b[i])
int dp[500005];
int a[500005],b[500005];
inline double slope(int l,int r){
	if(X(l)==X(r))return (Y(r)-Y(l))*1e9;
	return (Y(r)-Y(l))*1.0/(X(r)-X(l));
}
std::deque<int>q;
int n,ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;scanf("%d",&a[i++]));
	for(int i=1;i<=n;scanf("%d",&b[i++]));
	q.push_back(1);//从 1 号岛开始
	for(int i=2;i<=n;++i){
		while(q.size()>1&&slope(q[0],q[1])>=-a[i])q.pop_front();//把斜率比当前切线大的直接删掉
		dp[i]=dp[q[0]]/2+a[i]*a[q[0]]-b[q[0]];//最优决策点转移
		while(q.size()>1&&slope(*(q.end()-2),q.back())<=slope(q.back(),i))q.pop_back();//维护斜率单减
		q.push_back(i);
		ans=std::max(ans,dp[i]);
	}
	printf("%d",ans);
	return 0;
}
/*
dp[i]=dp[j]/2+a[i]*a[j]-b[j]
dp[j]/2-b[j]=-a[i]*a[j]+dp[i]
*/