题解 Nowcoder 5447C - 张老师的旅行

题解 #

观察易知，若想用最小的时间覆盖一段线段，那么结束时的位置一定在线段的左端点或右端点。那么我们的 dp 状态就可以设为 $dp_{l,r,p}$ ，代表覆盖从 l 到 r 的线段所用的最短时间并且以左端点结尾（p=0），右端点结尾（p=1）。

状态转移是不难想的， $dp_{l,r,0}$ 可以由 $dp_{l+1,r,0}$ 或 $dp_{l+1,r,1}$ 得到，同理 $dp_{l,r,1}$ 可以由 $dp_{l,r-1,0}$ 或 $dp_{l,r-1,1}$ 得到，别忘了判断一下是否在规定的时间之内。具体转移看代码～

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define pb push_back
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
 
const int N=1005;
int dp[N][N][2];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int> p(n+1),t(n+1);
    ms(dp,INF);
    for1(i,n){
        cin>>p[i];
        dp[i][i][0]=dp[i][i][1]=0;
    }
    for1(i,n) cin>>t[i];
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            int t1=min(dp[l+1][r][0]+p[l+1]-p[l],dp[l+1][r][1]+p[r]-p[l]);
            int t2=min(dp[l][r-1][0]+p[r]-p[l],dp[l][r-1][1]+p[r]-p[r-1]);
            if(t1<=t[l]) dp[l][r][0]=t1;
            if(t2<=t[r]) dp[l][r][1]=t2;
        }
    }
    int ans=min(dp[1][n][0],dp[1][n][1]);
    cout<<(ans==INF?-1:ans);
    return 0;
}