“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 C.张老师的旅行

C.张老师的旅行
链接：https://ac.nowcoder.com/acm/contest/5477/C

题目描述

张老师到了一个王国去旅游，王国有n个景点，张老师到达这个城市所在的车站恰好位于第x个景点，这个王国非常特别，恰好所有著名的景点都在分布在直线上，每个景点在坐标pi上(单位：公里)，张老师身体非常好，每走一公里花费一分钟。每个景点都有一个打卡点，并且必须在不迟于相应的时间（时间从张老师到达王国开始计算）前到达才能打卡成功并且给以一个打卡标记，集齐所这些标记就能获得一个大礼包。由于张老师非常想要大礼包，并且因为张老师还着急去下一个王国旅游，所以张老师希望用的时间尽量少，你能帮帮张老师吗？

输入描述:

输入的第一行，包含一个整数n（1≤n≤1000）。
第二行包含n个整数pi(1≤pi≤100000)，第i个整数pi为第i个景点的坐标（坐标从小到大排列）。
最后一行包含n个整数ti(0≤ti≤10,000,000)，ti表示第i个景点最迟到达的时间，时间为0则表示张老师所在车站的位置且只有一个为0。

输出描述:

输出所需的最少时间，若无解输出-1。

示例1
输入

4
1 2 3 4
0 1 2 3

输出

3

思路
我们把所有点放在数轴上，显然这些点被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方程：

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); 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); 

（如果看不太明白，可以上下画两条线段，自己模拟一下）
最短到达时间我们算出来了，只要对它跟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]); }