BZOJ3387 跨栏训练

Description

为了让奶牛参与运动，约翰建造了 $K$ 个栅栏。每条栅栏可以看做是二维平面上的一条线段，它们都平行于 X 轴。第 $i$ 条栅栏所覆盖的 X 轴坐标的区间为$[A_i,B_i]$，Y 轴高度就是 $i$。一开始，奶牛在坐标 $(S,K+1)$处，它们的家在原点处，所以要想要回家就必须“跨”一些栅栏。

但奶牛们是跨不过栅栏的，它们只能绕过栅栏。在二维平面上，它们只能沿水平和垂直方向移动，如果前进的道路上出现栅栏，它们就不能前进，必须沿水平方向移动到没有栅栏的地方再前进。奶牛们希望走的路越短越好，由于在垂直方向上的路程是确定的，你只需要帮它们求出在水平方向的最短路程就可以了。

Solution

贪心地想，如果当前走到了一个线段的尽头，最优的选择是不继续行走，横坐标停留在线段端点，因为如果要走的话，可以等到下次遇到线段时再走

并且从出发点走到原点的路程一定与从原点走到出发点的路程相同

设$dp_{i,0/1}$为从原点走到第$i$条线段的左/右端点需要走的最小距离，$j_1,j_2$分别为$i$线段左右端点正下方第一条线段的编号，转移需要从该线段来

$$dp_{i,0}=min(dp_{j,0}+|a_j-a_i|,dp_{j,1}+|b_j-a_i|)$$

$$dp_{i,1}=min(dp_{j,0}+|a_j-b_i|,dp_{j,1}+|b_j-b_i|)$$

将出发点视为一条$0$长线段

数据：链接：https://pan.baidu.com/s/1qmrkh7Myb1ggXN1XIEl_MQ 提取码：p7ht

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int k,s,a[100005],b[100005];
long long dp[100005][2];
struct Seg
{
    int val;
    bool tag;
}tree[800050];
inline int read()
{
    int f=1,w=0;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        w=(w<<1)+(w<<3)+ch-'0';
        ch=getchar();
    }
    return f*w;
}
void pushdown(int i,int l,int r)
{
    if(tree[i].tag)
    {
        tree[i<<1].val=tree[i<<1|1].val=tree[i].val;
        tree[i<<1].tag=tree[i<<1|1].tag=true;
        tree[i].tag=false;
    }
}
int query(int i,int l,int r,int p)
{
    if(l==r)
    {
        return tree[i].val;
    }
    pushdown(i,l,r);
    int mid=l+r>>1;
    if(p<=mid)
    {
        return query(i<<1,l,mid,p);
    }
    return query(i<<1|1,mid+1,r,p);
}
void update(int i,int l,int r,int L,int R,int v)
{
    if(L<=l&&r<=R)
    {
        tree[i]=(Seg){v,true};
        return;
    }
    pushdown(i,l,r);
    int mid=l+r>>1;
    if(L<=mid)
    {
        update(i<<1,l,mid,L,R,v);
    }
    if(R>mid)
    {
        update(i<<1|1,mid+1,r,L,R,v);
    }
}
int main()
{
    k=read();
    s=read();
    for(int i=1;i<=k;i++)
    {
        a[i]=read();
        b[i]=read();
    }
    a[k+1]=b[k+1]=s;
    for(int i=1;i<=k+1;i++)
    {
        int temp1=query(1,1,200010,a[i]+100005),temp2=query(1,1,200010,b[i]+100005);
        dp[i][0]=min(dp[temp1][0]+abs(a[temp1]-a[i]),dp[temp1][1]+abs(b[temp1]-a[i]));
        dp[i][1]=min(dp[temp2][0]+abs(a[temp2]-b[i]),dp[temp2][1]+abs(b[temp2]-b[i]));
        if(a[i]+1<b[i])
        {
            update(1,1,200010,a[i]+100006,b[i]+100004,i);
        }
    }
    printf("%lld
",dp[k+1][0]);
    return 0;
}