题解：P10207 [JOI 2024 Final] 马拉松比赛 2 / Marathon Race 2

· · 题解

思路

在考场上我先看了看子任务一，也就是起点和终点均为 0，发现此时的最优策略是先跑到最右边的球的位置，然后往左一个一个拿。

但考场上我拿完子任务一的分就跑路了，没继续往下想。其实通过上面的思考不难发现，我们要在速度大的时候（也就是拿的球少的时候）尽量跑远一些的距离。以及如果我们经过一个球多次，最优策略是在最后一次拿它。

有了以上性质，我们不难发现在最优策略下，我们拿的球一定是一段前缀加上一段后缀，未拿的球是中间的一段连续段，第一个拿的球一定是第一个或最后一个。

那么，我们可以设计 dp 状态了，我们先将 x 数组去重并排序，设 dp_{l,r,0/1,0/1} 表示当前未拿球的区间为 x_l \sim x_r，第一个拿的球是 x_1/x_n，当前在 l/r 的最小代价。

考虑如何转移，我们发现当未拿球的区间为 x_l\sim x_r 时可以从两种情况转移过来，分别是 x_{l-1}\sim x_r 和 x_l\sim x_{r+1}。那么状态转移方程就很简单了，我这里就不赘述了，可以去代码看。

有了状态转移方程，我们就可以进行区间 dp 了，但我们发现这样区间 dp 是 O(N^2) 的，但 N 的范围达到了 5\times 10^5，显然会超。

那我们想想，N 真的需要这么多吗？我们将 x 数组去重后，如果 N 还是很大，使答案超出 T 的范围，我们是不是就可以直接输出 No 了？

我们设去重后的 N 为 m，那么答案最少为 1+2+\dots+m，即 \frac{m(m+1)}{2}，如果它超过了 T 的范围，也就是 5\times 10^5，就可以直接输出 No 了，算出来大概是 m\geq 1000，这样我们的复杂度就是 O(m^2) 了。

预处理完了，该想想怎么求答案了，对于每种起点和终点，我们需要确定第一个和最后一个拿的球。前者很简单，只有 x_1 和 x_n 两种情况，取 min 即可。对于后者，我们肯定要找离终点最近的位置。那么，我们找到第一个大于等于终点的位置和最后一个小于等于终点的位置，对两种情况取 min 即可。不要忘了加上拿球的时间。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,q,s,g,t,ans,sum[500005],x[500005],dp[1005][1005][2][2];
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x[i];
        sum[x[i]]++;
    }
    for(int i=1;i<=m;i++){
        sum[i]+=sum[i-1];
    }
    sort(x+1,x+n+1);
    n=unique(x+1,x+n+1)-x-1;
    cin>>q;
    if(n>=1000){
        while(q--){
            cout<<"No\n"; 
        }
        return 0;
    }
    memset(dp,0x3f,sizeof(dp));
    dp[1][n][0][0]=dp[1][n][1][1]=0;
    for(int len=n-1;len>=1;len--){
        for(int l=1;l<=n-len+1;l++){
            int r=l+len-1;
            int s=sum[x[l]-1]+sum[m]-sum[x[r]]+1;
            for(int i=0;i<=1;i++){
                dp[l][r][i][0]=min(dp[l-1][r][i][0]+s*(x[l]-x[l-1]),dp[l][r+1][i][1]+s*(x[r+1]-x[l]));
                dp[l][r][i][1]=min(dp[l-1][r][i][0]+s*(x[r]-x[l-1]),dp[l][r+1][i][1]+s*(x[r+1]-x[r]));
            }
        }
    }
    while(q--){
        cin>>s>>g>>t;
        ans=INT_MAX;
        if(g<=x[n]){
            int i=lower_bound(x+1,x+n+1,g)-x;
            ans=min(ans,dp[i][i][0][0]+abs(s-x[1])+(sum[m]+1)*abs(x[i]-g));
            ans=min(ans,dp[i][i][1][0]+abs(s-x[n])+(sum[m]+1)*abs(x[i]-g));
        }
        if(x[1]<=g){
            int i=upper_bound(x+1,x+n+1,g)-x-1;
            ans=min(ans,dp[i][i][0][0]+abs(s-x[1])+(sum[m]+1)*abs(x[i]-g));
            ans=min(ans,dp[i][i][1][0]+abs(s-x[n])+(sum[m]+1)*abs(x[i]-g));
        }
        if(ans+sum[m]<=t){
            cout<<"Yes\n";
        }
        else{
            cout<<"No\n";
        }
    }
    return 0;
}