C.张老师的旅行

我们把所有点放在数轴上，显然这些点被k点分为两各部分，不妨设这左右两部分为b[N],c[N],并用b[i].len表示左边各点到k点距离，用c[j].len表示右边各个点到k点距离，b[i].t和c[j].t表示该点最晚到达时间，然后b[N],c[N]分别按到k点距离排序，这样我们得到两组数据，再对这两组数据进行dp，
我们设dp[i][j]为完成b（左）中前i个点，和c（右）中前j个点的最小时间，但是我们考虑到最终的落脚点可以在b（左边）中，也可在c（右边）中，所以加上两种状态，表示落脚点在哪一边，即dp[i][j][2],我们可以写出dp方程：


（如果看不太明白，可以上下画两条线段，自己模拟一下）
最短到达时间我们算出来了，只要对它跟b[i].t或c[j].t比较，就可以判断是否合法即：

if(dp[i][j][0]>b[i].t&&dp[i][j][1]>c[j].t){cout<<-1;return;}

当然如果只有一个不合法，我们要将该状态变为INF，消除它对后面的影响即：

if(dp[i][j][0]>b[i].t)dp[i][j][0]=INF;
if(dp[i][j][1]>c[j].t)dp[i][j][1]=INF;

附代码

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int dp[1001][1001][2];
struct node{
    int t=0,l=0;
}a[1001],b[1001],c[1001];
bool cmp(node x,node y){return x.l<y.l;}
int main(){
     int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].l;
    for(int i=1;i<=n;i++)cin>>a[i].t;
    sort(a+1,a+1+n,cmp);
    int k;
    for(int i=1;i<=n;i++){
        if(a[i].t==0)k=i;
    }
    memset(dp,INF,sizeof(dp));
    int x=0,y=0;
    dp[0][0][1]=dp[0][0][0]=0;
    for(int i=k-1;i>0;i--)x++,b[x].l=abs(a[i].l-a[k].l),b[x].t=a[i].t;//求左边点集
    for(int i=k+1;i<=n;i++)y++,c[y].l=abs(a[i].l-a[k].l),c[y].t=a[i].t;//求右边点集
    for(int i=0;i<=x;i++){
        for(int j=0;j<=y;j++){
            if(i)dp[i][j][0]=min(dp[i-1][j][0]+b[i].l-b[i-1].l,dp[i-1][j][1]+c[j].l+b[i].l);
            if(j)dp[i][j][1]=min(dp[i][j-1][1]+c[j].l-c[j-1].l,dp[i][j-1][0]+c[j].l+b[i].l);
            if(dp[i][j][0]>b[i].t&&dp[i][j][1]>c[j].t){cout<<-1;return 0;}
            if(dp[i][j][0]>b[i].t)dp[i][j][0]=INF;
            if(dp[i][j][1]>c[j].t)dp[i][j][1]=INF;
        }
    }
    cout<<min(dp[x][y][0],dp[x][y][1]);
}