【AtCoder Grand Contest 007 D】Shik and Game

mrsrz 2月 07, 2020

单调队列优化 DP。

题目大意：

在数轴上有 $n$ 个关键点，你在点 $0$，终点在点 $E$。保证关键点在 $0\sim E$ 之间。

一个关键点从第一次经过的时刻算起，经过 $T$ 秒后会在那个点处产生一个金币。

你要从 $0$ 走到 $E$，并拿到所有金币。每秒可以向左或向右走一格。问至少需要多少秒。

题解：

令 $f_i$ 表示走到关键点 $i$，并拿到前 $i$ 枚金币的最小时刻。我们走的路径显然分成若干段，每段由：左到右（碰到关键点），右到左（回到左边），左到右（拿金币）组成。

设 $p_i$ 为关键点的位置（令 $p_0=0$），则：

$\begin{align} f_i&=\min_j\{f_j+(p_i-p_j)+\max(T,2(p_i-p_{j+1}))\}\\ &=\min_j\{f_j-p_j+3p_i+\max(T-2p_i,-2p_j)\} \end{align}$

转移的时候我们考虑 $\max$ 里的东西，其中一个临界点为 $T-2p_i$，这是一个和 $i$ 有关的常数。

对于所有的状态 $j$，我们显然存在一个点 $p$ 满足当 $1\leq j\leq p$ 时，$T-2p_i<-2p_j$，而当 $p\lt j\lt i$ 时，$T-2p_i\geq -2p_j$。

对于 $-2p_j$ 作为取值的，显然每次都用最优的那个更新。动态更新之前的最优值即可。

对于 $T-2p_i$ 作为取值的，我们取这个区间里的最优的更新。单调队列优化即可。

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

Code：

#include<cstdio>
#include<algorithm>
const int N=1e5+5;
typedef long long LL;
int n,E,T,p[N];
LL dp[N];
int q[N],h,t;
int main(){
    scanf("%d%d%d",&n,&E,&T);
    for(int i=1;i<=n;++i)scanf("%d",p+i),dp[i]=0x7fffffffffffffff;
    int pre=0,mpos=0;
    for(int i=1;i<=n;++i){
        const int TL=T-2*p[i];
        while(h<t&&TL<=-2*p[q[h]+1])++h;
        int j=q[h];
        dp[i]=dp[j]-p[j]+std::max(TL,-2*p[j+1])+3LL*p[i];
        while(pre<i&&TL<=-2*p[pre+1]){
            if(dp[mpos]-p[mpos]-2LL*p[mpos+1]>dp[pre]-p[pre]-2LL*p[pre+1])
            mpos=pre;
            ++pre;
        }
        j=mpos;
        dp[i]=std::min(dp[i],dp[j]-p[j]+std::max(TL,-2*p[j+1])+3LL*p[i]);
        while(h<=t&&dp[q[t]]-p[q[t]]>=dp[i]-p[i])--t;
        q[++t]=i;
    }
    printf("%lld\n",dp[n]+E-p[n]);
    return 0;
}