题解：P10726 [GESP202406 八级] 空间跳跃

Solwek · 2024-07-09 18:26:38 · 题解

一道很神奇的题目，感觉什么算法都行。

由于 n\le 1000 并且联系题目，我们很难不想到 dp，设 f_{i,0} 表示已经来到第 i 层，并且在左端点的最少时间，f_{i,1} 表示已经来到第 i 层，并且在右端点的最少时间。

状态转移显然，我们只需要枚举 i 从左端点落到的板子编号和右端点落到的板子编号进行转移，以左端点举例：（设落下去的板子编号为 j）。

转移条件为 j 是第一个满足 l_j\le l_i\le r_j 并且 h_i\ge h_j 条件的板子编号。

初值为 f_{s,0}=0,f_{s,1}=r_s-l_s。

但由于题目并未保证 h_i\ge h_{i+1}，所以我们要先排序，再 dp，并且 s,t 也要变成新序列的编号。

时间复杂度应该是 O(n^2)。

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;

struct node{
    int l,r,h,id;
}a[1010];
int dp[1010][2];
bool cmp(node x,node y){
    if(x.h==y.h)return x.l<y.l;
    return x.h>y.h;
}
signed main(){  
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,os,ot;
    cin>>n>>os>>ot;
    for(int i=1;i<=n;i++)
        cin>>a[i].l>>a[i].r>>a[i].h,a[i].id=i,dp[i][0]=dp[i][1]=1e18;
    sort(a+1,a+n+1,cmp);
    int s,t;
    for(int i=1;i<=n;i++){
        if(a[i].id==os)s=i;
        if(a[i].id==ot)t=i;
    }
    dp[s][0]=0,dp[s][1]=a[s].r-a[s].l;
    int ans=1e18;
    for(int i=s;i<=t;i++){
        for(int j=i+1;j<=t;j++){
            if(a[i].l>=a[j].l&&a[i].l<=a[j].r&&a[i].h>a[j].h){
                int val=a[i].h-a[j].h;
                if(j==t)ans=min(ans,dp[i][0]+val);
                dp[j][0]=min(dp[j][0],dp[i][0]+a[i].l-a[j].l+val);
                dp[j][1]=min(dp[j][1],dp[i][0]+a[j].r-a[i].l+val);
                break;
            }
        }
        for(int j=i+1;j<=t;j++){
            if(a[i].r>=a[j].l&&a[i].r<=a[j].r&&a[i].h>a[j].h){
                int val=a[i].h-a[j].h;
                if(j==t)ans=min(ans,dp[i][1]+val);
                dp[j][0]=min(dp[j][0],dp[i][1]+a[i].r-a[j].l+val);
                dp[j][1]=min(dp[j][1],dp[i][1]+a[j].r-a[i].r+val);
                break;
            }
        }
    }
    if(ans==1e18)cout<<"-1\n";
    else cout<<ans<<'\n';
    return 0;
}