苏州网站推广,组建网站建设团队,佳木斯做微网站,用jsp做网站的难点首先#xff0c;很容易想到Dp。设f[i][0]表示第i个栅栏走左边的最短路#xff0c;f[i][1]表示第i个栅栏走右边的最短路。 所以#xff0c;我们要找一个刚好在第i个栅栏的左右边界下面的栅栏。如图所示#xff1a; 则有#xff1a; f[i][0] min(f[k][0] |Left[i] - Left[… 首先很容易想到Dp。设f[i][0]表示第i个栅栏走左边的最短路f[i][1]表示第i个栅栏走右边的最短路。 所以我们要找一个刚好在第i个栅栏的左右边界下面的栅栏。如图所示 则有 f[i][0] min(f[k][0] |Left[i] - Left[k]| , f[k][1] |Left[i] - Right[k]| ) f[i][1] min(f[j][0] |Right[i] - Left[j]| , f[j][1] |Right[i] - Right[j]| ) 那么该怎样求k和j呢 很容易想到开一个数组从小到大覆盖。但这样的时间复杂度是On^2的。用线段树区间修改单点查询就可以了。 附上程序 #include cstdio
#include iostream
#include cstring
#include algorithm
#include string
#include cstdlib
#include bitset
#include fstream
#include queue
#include stack
#include map
#include set
#include ctime
#include deque
#include vector
#include complex
#include utility
using namespace std;
typedef long long LL;
#define INF 0x3fffffff
#define Maxn 100010int num[Maxn1];
int f[Maxn][2];int n,m;int a[Maxn],b[Maxn];#define L(u) u1
#define R(u) u1|1struct Tnode{int l,r;bool isset;int set;
};
Tnode tr[Maxn3];void build(int u,int l,int r)
{tr[u].l l; tr[u].r r;tr[u].isset true; tr[u].set 0;if(lr){int mid (lr)1;build(L(u),l,mid);build(R(u),mid1,r);}
}void pushdown(int u)
{if(tr[u].isset){tr[L(u)].isset tr[R(u)].isset true;tr[L(u)].set tr[R(u)].set tr[u].set;tr[u].isset tr[u].set 0;}
}void update(int u,int l,int r,int val)
{if(ltr[u].l tr[u].rr){tr[u].isset true;tr[u].set val;return;}pushdown(u);int mid (tr[u].ltr[u].r)1;if(midl) update(L(u),l,r,val);if(midr) update(R(u),l,r,val);
}int query(int u,int p)
{if(tr[u].ltr[u].r)return tr[u].set;pushdown(u);int mid (tr[u].ltr[u].r)1;if(pmid) return query(L(u),p);else return query(R(u),p);
}int main()
{ scanf(%d%d,n,m);build(1,1,Maxn1);a[n1] b[n1] m;for(int i1;in;i)scanf(%d%d,a[i],b[i]);int k1,k2;for(int i1;in1;i){k1 query(1,a[i]100005);k2 query(1,b[i]100005);f[i][0] min(f[k1][0]abs(a[i]-a[k1]),f[k1][1]abs(a[i]-b[k1]));f[i][1] min(f[k2][0]abs(b[i]-a[k2]),f[k2][1]abs(b[i]-b[k2]));if(a[i]1b[i])update(1,a[i]1000051,b[i]100005-1,i);}printf(%d\n,f[n1][0]);return 0;
}转载于:https://www.cnblogs.com/ouqingliang/p/9245248.html
