P8726 [蓝桥杯 2020 省 AB3] 旅行家 题解

Super_Cube · 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 有序的做法。

我们对于上式进行换元：

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

我们为了让 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]
*/