网站开发要计入无形资产吗,玻璃钢产品哪个网站做推广好,成功营销十大经典案例,如何免费域名注册正题 题目大意
一个平面上#xff0c;起点是(0,0)(0,0)(0,0)#xff0c;终点是(0,t)(0,t)(0,t)。有nnn个没有共同面积的矩形障碍物#xff0c;对于每个障碍物不可以从内部穿过而可以从边上走过。求最短路。 解题思路
因为没有共同面积所以横坐标不会变小。并且只有在边界处…正题 题目大意
一个平面上起点是(0,0)(0,0)(0,0)终点是(0,t)(0,t)(0,t)。有nnn个没有共同面积的矩形障碍物对于每个障碍物不可以从内部穿过而可以从边上走过。求最短路。 解题思路
因为没有共同面积所以横坐标不会变小。并且只有在边界处才会拐弯。
对于每个矩形在后面的那条线是没有用的因为必然在前面那条线处就走到了之外的位置然后只会往右走所以不会再走回矩形内部。
所以我们对于每个矩形左边的上下两个点作为拐点然后用扫描线计算每个点的前驱点也就是从哪条边界到达的然后dpdpdp计算即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N5e510;
struct node{ll x,l,r;
}l[N];
ll n,tot,cnt,b[N*2],pre[N][2],f[N][2];
ll w[N*8],lazy[N*8];
void Downdata(ll x){if(!lazy[x])return;w[x*2]w[x*21]lazy[x*2]lazy[x*21]lazy[x];lazy[x]0;return;
}
void Change(ll x,ll L,ll R,ll l,ll r,ll val){if(LlRr){lazy[x]w[x]val;return;}ll mid(LR)1;Downdata(x);if(rmid)Change(x*2,L,mid,l,r,val);else if(lmid)Change(x*21,mid1,R,l,r,val);else Change(x*2,L,mid,l,mid,val),Change(x*21,mid1,R,mid1,r,val);return;
}
ll Ask(ll x,ll l,ll r,ll pos){if(lr)return w[x];ll mid(lr)1;Downdata(x);if(posmid)return Ask(x*2,l,mid,pos);return Ask(x*21,mid1,r,pos);
}
bool cmp(node x,node y)
{return x.xy.x;}
int main()
{
// freopen(speike.in,r,stdin);
// freopen(speike.out,w,stdout);ll xt;b[cnt]0;scanf(%lld%lld,n,xt);l[tot](node){0,0,0};l[tot](node){xt,0,0};for(ll i1;in;i){ll x1,y1,x2,y2;scanf(%lld%lld%lld%lld,x1,y1,x2,y2);if(y1y2)swap(y1,y2);b[cnt]y1;b[cnt]y2;l[tot](node){x1,y1,y2};}sort(b1,b1cnt);cntunique(b1,b1cnt)-b-1;sort(l2,l1tot,cmp);for(ll i1;itot;i){l[i].llower_bound(b1,b1cnt,l[i].l)-b;l[i].rlower_bound(b1,b1cnt,l[i].r)-b; }for(ll i1;itot;i){pre[i][0]Ask(1,1,cnt,l[i].l);pre[i][1]Ask(1,1,cnt,l[i].r);Change(1,1,cnt,l[i].l,l[i].r,i);}for(ll i2;itot;i){ll xmax(1ll,pre[i][0]);f[i][0]min(f[x][0]abs(b[l[i].l]-b[l[x].l]),f[x][1]abs(b[l[i].l]-b[l[x].r]));ll ymax(1ll,pre[i][1]);f[i][1]min(f[y][0]abs(b[l[i].r]-b[l[y].l]),f[y][1]abs(b[l[i].r]-b[l[y].r]));}printf(%lld,min(f[tot][0],f[tot][1])xt);
}
