ABC273F
*2277
题意
高桥在数轴原点，他想走到坐标 \(X\)。
数轴上有 \(N\) 面墙和 \(N\) 把锤子。
- 第 \(i\) 面墙位于坐标 \(Y_i\)，高桥不能穿墙。
- 第 \(i\) 把锤子位于坐标 \(Z_i\)。
- 高桥路过有锤子的坐标时会捡起锤子。
- 第 \(i\) 把锤子可以把第 \(i\) 面墙锤烂，然后高桥就可以过去了。
判断高桥是否可以达成目标，如果可以，找出最小移动距离。
- \(1≤N≤1500\)
- \(1≤∣X∣,∣Y_i∣,∣Z_i∣≤10^9\)
- 坐标两两不同
题解
注意到 “路过锤子就可以捡起来”，说明只需要知道左右两边最远到过的位置，即可得知当前持有锤子的情况。而随着锤子的增多容易发现左右端点会不断扩展（除非无解），考虑 DP。
将起点、终点、锤子坐标、墙坐标放在一起排序，就可以获得数轴上的分布情况；从起点开始，每次我们都会试图向左或向右扩展一个端点，可以是到达终点、捡锤子，在墙对应的锤子已经被捡起时可以到达墙。
考虑记 \(f_{l,r}\) 表示左端点为 \(l\)，右端点为 \(r\) 时到终点还需要走的距离。按理这样可以记录下当前的所有锤子，但是不好确定当前在哪个位置，如果加一维 \(p\) 记录当前所在的坐标复杂度就不能接受了。
注意到每次都是向左或向右用脚去扩展端点，并且为了最小化答案我们不会无故反复横跳。所以每次扩展完端点，当前位置一定会在两个端点中的一个上。多开一维 \(p ∈ {0,1}\) 表示当前在 \(l\) 还是 \(r\) 即可。
转移的话，如果接下来要扩展的点不是墙那么就可以直接走过去；反之需要检查对应的锤子在不在手上，如果在就可以走。
时间复杂度 \(O(n^2)\)。
代码
使用记忆化搜索实现。
const ll maxn=1.5e3+5;
struct node{
ll id,ty,p;
friend bool operator < (const node &x,const node &y){
return x.p<y.p;
}
}a[maxn<<1];
ll k[maxn];
ll n,tot,fin;
ll f[maxn<<1][maxn<<1][2];
ll dfs(ll x,ll y,bool cur){
if(a[x].ty==0||a[y].ty==0){
if((a[x].ty==0&&cur==0)||(a[y].ty==0&&cur==1)){
return 0;
}
return dfs(x,y,cur^1)+a[y].p-a[x].p;
}
if(~f[x][y][cur])return f[x][y][cur];
ll res=1ll<<60;
if(x-1){
if(a[x-1].ty!=1){
res=min(res,dfs(x-1,y,0)+a[x].p-a[x-1].p+(cur==0?0:a[y].p-a[x].p));
}
else if(k[a[x-1].id]>=a[x].p&&k[a[x-1].id]<=a[y].p){
res=min(res,dfs(x-1,y,0)+a[x].p-a[x-1].p+(cur==0?0:a[y].p-a[x].p));
}
}
if(y+1<=tot){
if(a[y+1].ty!=1){
res=min(res,dfs(x,y+1,1)+a[y+1].p-a[y].p+(cur==1?0:a[y].p-a[x].p));
}
else if(k[a[y+1].id]>=a[x].p&&k[a[y+1].id]<=a[y].p){
res=min(res,dfs(x,y+1,1)+a[y+1].p-a[y].p+(cur==1?0:a[y].p-a[x].p));
}
}
return f[x][y][cur]=res;
}
void solve(){
n=R,fin=R;
a[++tot].id=0;
a[tot].ty=0,a[tot].p=fin;
a[++tot].id=0;
a[tot].ty=3,a[tot].p=0;
for(ll i=1;i<=n;i++){
a[++tot].id=i;
a[tot].ty=1;
a[tot].p=R;
}
for(ll i=1;i<=n;i++){
a[++tot].id=i;
a[tot].ty=2;
a[tot].p=R;
k[i]=a[tot].p;
}
sort(a+1,a+1+tot);
memset(f,-1,sizeof(f));
ll s=0;
for(ll i=1;i<=tot;i++){
if(a[i].ty==3){
s=i;
break;
}
}
ll ans=dfs(s,s,0);
if(ans>=(1ll<<60))puts("-1");
else we(ans);
return ;
}