C张老师的旅行 dp

观察发现，在最少时间的前提下走过的点必然是连续的区间设为[l,r]，那么唯一的变化就是终点落在l还是人r，这样我们可以通过dp来解决，我们设状态f[l][r][0]表示终点落在l的前提下走完区间[l,最小时间，f[l][r][1]同理终点落在r上，状态转移为：
f[l-1][r][0]=min(f[l-1][r][0],f[l][r][0]+p[l]-p[l-1]);
f[l][r+1][1]=min(f[l][r+1][1],f[l][r][0]+p[r+1]-p[l]);
f[l-1][r][0]=min(f[l-1][r][0],f[l][r][1]+p[r]-p[l-1]);
f[l][r+1][1]=min(f[l][r+1][1],f[l][r][1]+p[r+1]-p[r]);
那么答案就是min（f[1][n][0]，f[1][n][1]）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[1010][1010][2];
const int INF = 0x3f3f3f3f;
int tlimit[1010];
int pos[1010];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>pos[i];
    for(int i=0;i<n;i++)cin>>tlimit[i];
    memset(dp,0x3f,sizeof(dp));
    for(int i=0;i<n;i++)if(tlimit[i]==0){
        dp[i][i][0]=dp[i][i][1]=0;

    }
    for(int len=1;len<n;len++){
        for(int l=0;l<n-len;l++){
            int r=l+len;
            int t = dp[l+1][r][0] + pos[l+1] - pos[l];
            if(t<=tlimit[l] && t<dp[l][r][0])dp[l][r][0]=t;
            t = dp[l+1][r][1] + pos[r] - pos[l];
            if(t<=tlimit[l] && t<dp[l][r][0])dp[l][r][0]=t;

            t = dp[l][r-1][0] + pos[r] - pos[l];
            if(t<=tlimit[r] && t<dp[l][r][1])dp[l][r][1]=t;
            t = dp[l][r-1][1] + pos[r] - pos[r-1];
            if(t<=tlimit[r] && t<dp[l][r][1])dp[l][r][1]=t;
        }
    }
    int ans = min(dp[0][n-1][0],dp[0][n-1][1]);
    if(ans==INF)ans = -1;
    cout<<ans<<endl;
    return 0;
}