贪心地走到最顶或最底端dp

题目传送门

大致思路

要想路径最短,肯定在 $x$ 轴上不会走回头路
$y$ 轴上只会走到当前 $x$ 坐标的最顶端或最底端,否则会出现重复走一段路的情况
记$dp_{i,0},dp_{i,1}$分别为 $x$ 坐标为 $i$ 且走到最顶端 , 或最底端的最小步数
那么有
$dp_{i,0}=min(dp_{[i-1][0]}+abs(a_{[i-1][0]}-a_{[i][1]}),dp_{[i-1][1]}+abs(a_{[i-1][1]}-a_{[i][1]}))+a_{[i][0]}-a_{[i][1]}$
$dp_{i,1}=min(dp_{[i-1][0]}+abs(a_{[i-1][0]}-a_{[i][0]}),dp_{[i-1][1]}+abs(a_{[i-1][1]-a_{[i][0]}}))+a_{[i][0]}-a_{[i][1]}$
其中$a_{[i][0]},a_{[i][1]}$是 $x$ 坐标为 $i$ 时的最顶端和最底端的 $y$ 值

Code

void solve() {
    int n,ax,ay,bx,by;
    cin >> n >> ax >> ay>> bx >>by;
    vector<array<int,2>> p(n);
    for (int i=0;i<n;i++) cin >>p[i][0];
    for (int i=0;i<n;i++) cin >> p[i][1];
    sort(all(p));
    int ans=bx-ax;
    set<int> s;
    for (int i=0;i<n;i++) s.insert(p[i][0]);
    int sz=s.size();
    vector<array<int,2>> a(sz+1);//各列的y值最大最小值
    a[0]={ay,ay};
    int now=1;
    int cur=p[0][0];
    int mx=LLONG_MIN;
    int mn=LLONG_MAX;
    for (int i=0;i<n;i++) {
        if (p[i][0]==cur) {
            mx=max(mx,p[i][1]);
            mn=min(mn,p[i][1]);
        }
        else {
            a[now++]={mx,mn};
            cur=p[i][0];
            mx=LLONG_MIN;
            mn=LLONG_MAX;
            mx=max(mx,p[i][1]);
            mn=min(mn,p[i][1]);
        }
    }
    a[now++]={mx,mn};
    a.pb({by,by});
    vector<vector<int>> dp(sz+2,vector<int>(2));
    for (int i=1;i<sz+2;i++) {
        dp[i][0]=min(dp[i-1][0]+abs(a[i-1][0]-a[i][1]),dp[i-1][1]+abs(a[i-1][1]-a[i][1]))+a[i][0]-a[i][1];
        dp[i][1]=min(dp[i-1][0]+abs(a[i-1][0]-a[i][0]),dp[i-1][1]+abs(a[i-1][1]-a[i][0]))+a[i][0]-a[i][1];
    }
    ans+=min(dp[sz+1][0],dp[sz+1][1]);
    cout <<ans<<el;

}