Fence Obstacle Course

有n个区间自下而上有顺序的排列，标号\(1\sim n\)，第i个区间记做\([l_i,r_i]\)，现在从第n个区间的起点s出发（显然s在\([l_n,r_n]\)内），每次可以选择移动到所在区间的左端点或者右端点，然后跳下去，到达第一个碰到的区间，继续进行相同操作，定义第0个区间为无限延伸，求到第0个区间的位置0的最小水平移动距离，\(n\leq 50000,-1000000\leq l_i,r_i\leq 100000\)。

解

思路一

注意到每个区间到达另一个区间类似图，于是可以通过线段树维护，建出这张图，跑spfa或者dijsktra。

思路二

以区间为状态，设\(f[i][0/1]\)分别表示到达第i个区间左端点和右端点的最小水平移动距离，显然有

\[f[i][0]=\min_{i<j\leq n}\{f[j][0]+l_j-l_i(l_i\leq l_j\leq r_i),f[j][1]+r_j-l_i(l_i\leq r_j\leq r_i)\}
\]

\[f[i][1]=\min_{i<j\leq n}\{f[j][0]+r_i-l_j(l_i\leq l_j\leq r_i),f[j][1]+r_i-r_j(l_i\le r_j\leq r_i)\}
\]

注意被用过的决策点不能再使用

边界：\(f[n][0]=s-l_n,f[n][1]=r_n-s\)

答案：合法的可以到达此处的决策，具体看代码

于是注意到需要决策点的合法，于是考虑线段树+离散化维护

参考代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define il inline

#define ri register

#define Size 50050

#define intmax 33686018

#define v0 (void)0

using namespace std;

template<class free>

il free Min(free,free);

struct lsh{

	int a[Size],b[Size],n;

	il void prepare(int len,int ar[]){

		n=len;for(int i(1);i<=n;++i)a[i]=ar[i];

		sort(a+1,a+n+1);for(int i(1);i<=n;++i)b[i]=dfs(ar[i]);

	}

	il int dfs(int x){

		int l(1),mid,r(n);

		while(l<=r){

			mid=l+r>>1;

			if(a[mid]<x)l=mid+1;

			else r=mid-1;

		}return l;

	}

	il int dfs_(int x){

		int l(1),mid,r(n);

		while(l<=r){

			mid=l+r>>1;

			if(a[mid]>x)r=mid-1;

			else l=mid+1;

		}return l;

	}

}L,R;

struct segment_tree{

	struct DATA{

		bool a;

		int l,r,d;

	}t[Size<<2];

	void build(int p,int l,int r){

		t[p].l=l,t[p].r=r,t[p].d=intmax;

		if(l==r)return;int mid(l+r>>1),pl(p<<1),pr(pl|1);

		build(pl,l,mid),build(pr,mid+1,r);

	}

	il void spread(int p){

		if(t[p].a){

			int pl(p<<1),pr(pl|1);

			t[p].a=0,t[pl].a=t[pr].a=1;

			t[pl].d=t[pr].d=t[p].d;

		}

	}

	void change(int p,int l,int r,int v){

		if(l<=t[p].l&&t[p].r<=r)return t[p].a=1,t[p].d=v,v0;

		spread(p);int mid(t[p].l+t[p].r>>1),pl(p<<1),pr(pl|1);

		if(l<=mid)change(pl,l,r,v);if(mid<r)change(pr,l,r,v);

		t[p].d=Min(t[pl].d,t[pr].d);

	}

	int ask(int p,int l,int r){

		if(l<=t[p].l&&t[p].r<=r)return t[p].d;

		int mid(t[p].l+t[p].r>>1),pl(p<<1),pr(pl|1),ans(intmax);

		spread(p);if(l<=mid)ans=Min(ans,ask(pl,l,r));

		if(mid<r)ans=Min(ans,ask(pr,l,r));return ans;

	}

}l0,l1,r0,r1;

int l[Size],r[Size],dp[Size][2];

il void read(int&);

int main(){

	int n,s;read(n),read(s);

	for(int i(1);i<=n;++i)

		read(l[i]),read(r[i]);

	L.prepare(n,l),R.prepare(n,r);

	memset(dp,2,sizeof(dp));

	dp[n][0]=s-l[n],dp[n][1]=r[n]-s;

	l0.build(1,1,n),r0.build(1,1,n);

	l1.build(1,1,n),r1.build(1,1,n);

	l0.change(1,L.b[n],L.b[n],dp[n][0]+l[n]);

	r0.change(1,L.b[n],L.b[n],dp[n][0]-l[n]);

	l1.change(1,R.b[n],R.b[n],dp[n][1]+r[n]);

	r1.change(1,R.b[n],R.b[n],dp[n][1]-r[n]);

	for(int i(n-1),j,k;i;--i){

		j=L.dfs(l[i]),k=L.dfs_(r[i])-1;

		if(j<=k){

			dp[i][0]=Min(dp[i][0],l0.ask(1,j,k));

			dp[i][1]=Min(dp[i][1],r0.ask(1,j,k));

			l0.change(1,j,k,intmax),r0.change(1,j,k,intmax);

		}

		j=R.dfs(l[i]),k=R.dfs_(r[i])-1;

		if(j<=k){

			dp[i][0]=Min(dp[i][0],l1.ask(1,j,k));

			dp[i][1]=Min(dp[i][1],r1.ask(1,j,k));

			l1.change(1,j,k,intmax),r1.change(1,j,k,intmax);

		}dp[i][0]-=l[i],dp[i][1]+=r[i];

		l0.change(1,L.b[i],L.b[i],dp[i][0]+l[i]);

		r0.change(1,L.b[i],L.b[i],dp[i][0]-l[i]);

		l1.change(1,R.b[i],R.b[i],dp[i][1]+r[i]);

		r1.change(1,R.b[i],R.b[i],dp[i][1]-r[i]);

	}int j,k,ans(intmax);j=L.dfs(0),k=R.dfs(0);

	if(j<=n)ans=Min(ans,l0.ask(1,j,n));

	if(k<=n)ans=Min(ans,l1.ask(1,k,n));--j,--k;

	if(j)ans=Min(ans,r0.ask(1,1,j));

	if(k)ans=Min(ans,r1.ask(1,1,k));

	printf("%d",ans);

	return 0;

}

il void read(int &x){

	x&=0;ri char c;while(c=getchar(),c==' '||c=='\n'||c=='\r');

	ri bool check(false);if(c=='-')check|=true,c=getchar();

	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

	if(check)x=-x;

}

template<class free>

il free Min(free a,free b){

	return a<b?a:b;

}

思路三

注意到思路二枚举了太多了不合法的状态，而且状态被用过还不能再用了，于是考虑倒推，设\(f[i][0/1]\)分别表示从第i个区间到达终点的最短水平移动距离，那么有

\[f[i][0]=\min_{1\leq j<i,l_j\leq l_i\leq r_j}(f[j][0]+l_i-l_j,f[j][1]+r_j-l_i)
\]

\[f[i][1]=\min_{1\leq j<i,l_j\leq r_i\leq r_j}(f[j][0]+r_i-l_j,f[j][1]+r_j-r_i)
\]

而且每个状态对应的决策点只有一组，于是可以考虑线段树维护每个位置可对应的决策点，而位置范围只有2000000，于是直接暴力建树即可，这样建的树只要一棵。

#include <iostream>

#include <cstdio>

#include <cstring>

#define il inline

#define ri register

#define Size 50050

#define v0 (void)0

using namespace std;

struct segment_tree{

    struct DATA{

        bool is;

        int l,r,d;

    }t[800000];

    void build(int p,int l,int r){

        t[p].l=l,t[p].r=r;if(l==r)return;

        int mid(l+r>>1),pl(p<<1),pr(pl|1);

        t[p].d=-1,build(pl,l,mid),build(pr,mid+1,r);

    }

    il void spread(int p){

        if(t[p].is){

            int pl(p<<1),pr(pl|1);

            t[p].is=0,t[pl].is=t[pr].is=1;

            t[pl].d=t[pr].d=t[p].d;

        }

    }

    void change(int p,int l,int r,int v){

        if(l<=t[p].l&&t[p].r<=r)return t[p].d=v,t[p].is=1,v0;

        spread(p);int mid(t[p].l+t[p].r>>1),pl(p<<1),pr(pl|1);

        if(l<=mid)change(pl,l,r,v);if(mid<r)change(pr,l,r,v);

		t[p].d=-1;

    }

    int ask(int p,int x){

		if(t[p].d>=0)return t[p].d;spread(p);

        int mid(t[p].l+t[p].r>>1),pl(p<<1),pr(pl|1);

        return mid<x?ask(pr,x):ask(pl,x);

    }

}S;

int l[Size],r[Size],dp[Size][2];

il void read(int&);

template<class free>il free Abs(free);

template<class free>il free Min(free,free);

int main(){

    int n,s;

    read(n),read(s),S.build(1,-100000,100000);

	for(int i(1);i<=n;++i)read(l[i]),read(r[i]);

    for(int i(1),j;i<=n;++i){

        //read(l[i]),read(r[i]);

		j=S.ask(1,l[i]);

		if(j)dp[i][0]=Min(dp[j][0]+l[i]-l[j],dp[j][1]+r[j]-l[i]);

		else dp[i][0]=Abs(l[i]);j=S.ask(1,r[i]);

		if(j)dp[i][1]=Min(dp[j][0]+r[i]-l[j],dp[j][1]+r[j]-r[i]);

		else dp[i][1]=Abs(r[i]);S.change(1,l[i],r[i],i);

    }printf("%d",Min(s-l[n]+dp[n][0],r[n]-s+dp[n][1]));

    return 0;

}

template<class free>

il free Abs(free x){

	return x<0?-x:x;

}

template<class free>

il free Min(free a,free b){

	return a<b?a:b;

}

il void read(int &x){

    x&=0;ri char c;while(c=getchar(),c==' '||c=='\n'||c=='\r');

    ri bool check(false);if(c=='-')check|=true,c=getchar();

    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

    if(check)x=-x;

}

巴特西

Fence Obstacle Course

解

思路一

思路二

思路三

最新文章

热门文章