[DP记录]AT2171 [AGC007D] Shik and Game

**题意** ： 初始时 Shik 君在数轴的原点，出口坐标为 $E$ 。数轴上有 $n$ 只小熊，第 $i$ 只小熊在 $x_i$ 位置。 Shik 君拿着 $n$ 块糖果出发，每走一个单位长度要花费一秒。 到一个小熊的位置时，他可以送给这个小熊一块糖果，这个过程不花时间。 小熊收到糖果后， $T$ 秒以后会在它所在的位置产生一个金币。拾起所在位置的金币也不需要时间。 Shik 君想知道，他从出发到收集了所有金币抵达出口，最少要花费多长时间。 $n\leq 10^5,0< x_i< E$ ，时限$\texttt{2s}$。 ------------ 将 $x$ 从小到大排序。 考虑简化决策，注意到数轴上某个位置只能被经过奇数次。 若每个位置都只能被经过一次，那么策略将是单调的 ： 一直向右，在每个小熊处都等待直到拾得金币。这显然并非最优策略。 所以，我们应当允许适当的回头，在等待这只小熊的同时，先给后面的熊发糖，然后及时回来。 因此，同一个位置被经过三次是需要被允许的。但是若经过五次，可以调整为三次，且不会变劣，如下图 ：  其中红色表示最晚到达某一位置的方案，蓝色表示最早到达某一位置的方案。显然，红色越晚越好，蓝色越早越好。 下图中的红色均不早于上图中的红色，蓝色均不晚于上图中的蓝色，故不会更劣。 于是，我们有关键结论 ： 某个位置只有可能被经过一次或三次。 由此，可以考虑 $\rm DP$。 设 $f_i$ 表示 $1\sim i$ 的金币都已经拾起，且目前在 $x_i$ 位置的最小耗时。 转移时，枚举经过三次的一段小熊，则有 ： $$f_i=\min_{j=0}^{i-1}f_j+C(j,i)$$ 其中 $C(j,i)$ 是从 $x_j$ 出发，三次经过将 $[j+1,i]$ 中的熊都搞定所需时间。 有 $C(j,i)=x_i-x_j+\max\big(2(x_i-x_{j+1}),T\big)$。 其中 ，$2(x_i-x_{j+1})$ 指往返的代价， $T$ 指等待最后一只熊的代价。 无论如何转移， $x_i-x_j$ 的和都是 $E$ ，可以忽略， 于是有 $$f_i=\min_{j=0}^{i-1}f_j+\max\big(2(x_i-x_{j+1}),T\big)$$ 此时大力分类转移。 - $2(x_i-x_{j+1})\geq T$ 转移为 $f_i=\min_{j=0}^{i-1}f_j+2(x_i-x_{j+1})$ ，取 $f_j-2x_{j+1}$ 的最小值即可。 - $2(x_i-x_{j+1})\leq T$ 转移为 $f_i=\min_jf_j+T$ ，取 $f_j$ 的最小值即可。 其中，第一类转移的 $j$ 是一个前缀，且两种转移的分界线随着 $i$ 的增加单调右移。 于是，使用单调队列维护即可，复杂度 $O(n)$。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 100500 using namespace std; const ll INF=1ll<<60; int n,T,E,q[MaxN],x[MaxN]; ll f[MaxN],g[MaxN]; int main() { scanf("%d%d%d",&n,&E,&T); for (int i=1;i<=n;i++)scanf("%d",&x[i]); g[0]=-2*x[1];f[0]=0; int tl,tr;q[tl=tr=1]=0; for (int i=1,p=-1;i<=n;i++){ while(2*(x[i]-x[p+1])>=T)p++; while(tl<=tr&&q[tl]<p)tl++; f[i]=2*x[i]+((p>0) ? g[p-1] : INF); f[i]=min(f[i],T+f[q[tl]]); g[i]=min(g[i-1],f[i]-2*x[i+1]); while(tl<=tr&&f[q[tr]]>=f[i])tr--; q[++tr]=i; }printf("%lld",f[n]+E); return 0; } ```