[DP记录]CF1415F Cakes for Clones

**题意** ： 一条数轴上有一个人，他的移动速度为 $1$，每个时刻他可以让自己的坐标从 $x$ 变为 $x\pm1$、或者保持 $x$ 不变。 当他位于整点上时，他可以放置一个无法移动的分身，同时摧毁已经存在的分身（如果存在），放置分身不消耗时间。 初始时他位于 $0$，现在有 $n$ 个任务，每个任务 $(x_i,t_i)$ 要求他在 $t_i$ 时刻要么本人要么分身在 $x_i$ 坐标处。保证 $x$ 互不相同。 问是否存在合法方案，存在输出 `YES`，否则输出 `NO`。 $n\leq 5000$ ，时限$\texttt{3s}$。 ------------ 若已经确定了使用分身完成的任务集合（称为 B 类，本体完成的称为 A 类），考虑如何判定。 可绘制出如下图像，行动轨迹需要触碰到所有点和线段。  从早到晚枚举每个 A 类间隔，贪心地在其间触碰（未触碰的）直线（优先级从早到晚）。 讨论一下不难理解这种策略是对的。 ------------ 观察一段极长连续的 A 或 B 。（蓝色是不管 B 的路线，红色是管 B 的路线，左侧只需一段成真）  一段极长的 A 只可能对下一个 B 产生贡献。 一段极长的 B 的中间部分只能由前后两个 A 之间的空隙处理。（绿色框住的 B 可能已经被上一段 A 处理） - 对于一个需要处理的 B 连续段，从早到晚贪心访问之。 记第 $i$ 个 B 任务的时间区间为 $[l_i,r_i]$ （共有 $k$ 个）。 设初始时间为 $t$ ，位置为 $x$ 。下一步前往 $x_1$ ，时间为 $t+|x-x_1|$ ，若这个数 $>r_1$ 则无解，若这个数 $<l_1$ 则需要对 $l_1$ 取 $\max$ 。这样的 $t$ 一直是“最早时间”。 最后还需要能按时前往下一个 A 。 能发现，不必枚举 B 的连续段，可以一个个加入 B ，并维护“最早时间”。 于是可以设状态 $f_{i,0/1}$ 表示 $i$ 是 B 类，且 是/否 被前 $i-1$ 之前的间隙处理，所需的最小时间。 对于 $f_{i,0}$ ，则目前位置在 $x_i$ ；对于 $f_{i,1}$ ，$i-1$ 一定是 A 类，且目前位置在 $x_{i-1}$ 。 记 $g_{l\sim r}$ 表示从 $l$ 一路 A 到 $r$ 是否可能，是其间每个间隙的可能性与起来。 转移如下： 为了简便，记 $(a,b)=|x_a-x_b|$ 。 - $f_{i,0}$ - $i-1$ 是 B 类 - $f_{i-1,0}$ ： $f_{i,0}\leftarrow \max\big\{f_{i-1,0}+(i-1,i),l_i\big\}, \big(f_{i-1,0}+(i-1,i)\leq r_i\big)$ - $f_{i-1,1}$ ： $f_{i,1}\leftarrow \max\big\{f_{i-1,1}+(i-2,i),l_i\big\}, \big(f_{i-1,1}+(i-2,i)\leq r_i\big)$ - $i-1$ 是 A 类 ：枚举 A 类极长连续段 $[j+1,i-1]$ $f_{i,0}\leftarrow \max\big\{t_{i-1}+(i-1,i),l_i\big\}$ 条件是，存在 $j$ 满足： $(\min\big\{f_{j,1}+(j-1,j+1),f_{j,0}+(j,j+1)\big\}\leq t_{j+1})$ （ $j\rightarrow j+1$ 能接上） ${\ \bf and\ }g_{j+1\sim i-1}{\ \bf and\ }t_{i-1}+(i-1,i)\leq r_i$ （中间不会断、最后一步能到 $i$ ） - $f_{i,1}$ - $i-1$ 是 A 类 ：枚举 A 类极长连续段 $[j+1,i-1]$ $f_{i,1}\leftarrow t_{i-1}$ 条件是，存在 $j$ 满足： $(\min\big\{f_{j,1}+(j-1,j+1),f_{j,0}+(j,j+1)\big\}\leq t_{j+1})$ （ $j\rightarrow j+1$ 能接上） ${\ \bf and\ }g_{j+1\sim i-1}$ （中间不会断) ${\ \bf and\ }(\exists k\in[j+1,i-2],(i,k)+(i,k+1)\leq t_{k+1}-t_k{\ \bf or\ }\max\big\{\min\big\{f_{j,1}+(j-1,i),f_{j,0}+(j,i)\big\},t_j\big\}+(i,j+1)\leq t_{j+1})$ (存在一个中间空隙或者初始二连击搞定 $i$） 复杂度 $O(n^2)$ 。 ```cpp #include<algorithm> #include<cstdio> #define abs _abs #define ll long long #define MaxN 5050 using namespace std; const ll INF=1ll<<60; inline ll abs(int x){return x>0 ? x : -x;} struct Point{ll x,t;}p[MaxN]; inline ll det(int i,int j){return abs(p[i].x-p[j].x);} bool cmp(const Point &A,const Point &B){return A.t<B.t;} ll f[MaxN][2];int n;bool g[MaxN]; int main() { scanf("%d",&n);n+=2; p[1]=(Point){0,0};f[1][1]=INF; for (int i=2;i<n;i++)scanf("%lld%lld",&p[i].t,&p[i].x); p[n]=(Point){0,INF-1}; sort(p+1,p+n+1,cmp); for (int i=2;i<=n;i++){ g[i-1]=(det(i-1,i)<=p[i].t-p[i-1].t);// i-1 直走到 i 是否合法 f[i][0]=f[i][1]=INF; ll now=f[i-1][0]+det(i-1,i); if (now<=p[i].t)f[i][0]=min(f[i][0],max(now,(ll)p[i-1].t)); now=f[i-1][1]+det(i-2,i); if (now<=p[i].t)f[i][0]=min(f[i][0],max(now,(ll)p[i-1].t)); bool flag=0;//中间的空隙能否搞定 i for (int j=i-2;j;j--){ if (j+2<i){ flag|=det(i,j+1)+det(i,j+2)<=p[j+2].t-p[j+1].t; if (!g[j+1])break; } if (min(f[j][1]+det(j-1,j+1),f[j][0]+det(j,j+1))<=p[j+1].t){//能否 j -> j+1 if (flag||max(min(f[j][1]+det(j-1,i),f[j][0]+det(j,i)),(ll)p[j].t)+det(i,j+1)<=p[j+1].t)f[i][1]=p[i-1].t; if (g[i-1])f[i][0]=min(f[i][0],(ll)p[i-1].t+det(i-1,i)); } } }puts(min(f[n][0],f[n][1])<INF ? "YES" : "NO"); return 0; } ```