ARC120E 1D Party

· · 个人记录

找到最优策略：要么先向左遇到第一个人之后向右，要么先向右遇到第一个人之后向左（每个 i 都需要遇见一开始分别在他左右的两个人）

然后其实这个可以 直接转化为每个人一直向右或者向左，因为两个人相遇之后分别转向可以看作是互换了身份之后不转向继续走

然后盗个图，会发现整个局面变成了这样：

一种颜色就是一个人

然后结合图形可以写出一个 \text{dp}：

\large{ f_i = \min_{j = 2}^{i-2}\max(f_j,\dfrac{a_i-a_{j-1}}{2}) }

注意到这时候 f_i 的意义就是钦定 i 往左走，然后枚举上一个往左走的位置 j，这中间的都向右走并且 j-1 也向右走（一个三角形完全包含另一个三角形是不可能的，画个图就知道了），这里只枚举到 i-2 的原因是 i-1:L 的这个三角形 不完整，左边这条边遇到 i 之后还需要向右上延伸（可以看第一个三角形），所以不能算贡献

相应的这里要注意需要 \text{dp} 的时候特判 n，这是因为直接做的话 n-1 没有被 n 给 \text{dp} 到，但是 n 其实不需要向右上再延伸了，所以可以从 n-1 转移

考虑证明如下性质：

若 i 向右走，i+1 向左走，则称 i 是神奇的（？）。在最优策略中，不会出现 i 使得 i,i+1,i+2 都不神奇。

当 i 和 i+3 策略相反，如果这三者都不神奇，则 1. i+1 : L,i+2 :L，i+2 和 i+3 会在 i 和 i+3 折返后的交点处 相交；2. i+1:L,i+2:R，i+1,i+2 交于上述点；3. i+1:R,i+2:R，i 和 i+1 交于上述点。也就是说无论如何都会交于 i 和 i+3 的交点，而这时只需要把 i+1 \to R,i+2 \to L 就能早于这个点完成

这说明不会出现 \ge 4 个连续的方向相同的人，所以转移的决策点数从 O(n) 变成了 O(1)，很深奥（ 

#include <bits/stdc++.h>
using namespace std;
const int N = 200003;
int n,a[N],f[N];
main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",a+i);
    for(int i=2;i<=n;++i){
        f[i]=a[i]-a[1]>>1;
        for(int j=max(i-4,2);j<i-(i!=n);++j)
            f[i]=min(f[i],max(f[j],a[i]-a[j-1]>>1));
    }
    printf("%d",f[n]);
}