题解：区间dp。
(区间dp的基本解题方法：枚举长度+枚举起点（那么终点根据长度也就知道了）+枚举分割点)
但是本题并不需要枚举分割点，因为需要花费时间最短一定，那么一定是从所枚举的区间的一边一直走到另一边，那么是从左走到右还是从右走到左呢，这时我们就想到了dp开一维来放0,1，其中0表示从右到左，1表示从左到右。另外再开两维分别表示区间的左端点和右端点，根据题目(n)数据的大小，我们开(dpleft [ 1000 ight ]left [ 1000 ight ]left [ 2 ight ])
(dpleft [ i ight ]left [ j ight ]left [ 0 ight ]:表示从j到i的最短时间)
(dpleft [ i ight ]left [ j ight ]left [ 1 ight ]:表示从i到j的最短时间)
具体转移画图是很容易理解的，具体见代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e3+10; 5 const int inf = 0x3f3f3f3f; 6 const ll mod=1e9+7; 7 8 int dp[maxn][maxn][2]; 9 int pos[maxn],t[maxn]; 10 int n,st; 11 12 int main() 13 { 14 memset(dp,0x3f,sizeof(dp)); 15 scanf("%d",&n); 16 for(int i=1;i<=n;i++) scanf("%d",&pos[i]); 17 for(int i=1;i<=n;i++){ 18 scanf("%d",&t[i]); 19 if( !t[i] ){ 20 dp[i][i][0]=0; 21 dp[i][i][1]=0; 22 } 23 } 24 25 for(int len=1;len<n;len++){ 26 for(int l=1;l<=n-len;l++){ 27 int r=l+len; 28 ///dp[l][r][0] 29 int t1=dp[l+1][r][0]+(pos[l+1]-pos[l]); 30 if( t1<=t[l] ) dp[l][r][0]=min(dp[l][r][0],t1); 31 t1=dp[l+1][r][1]+(pos[r]-pos[l]); 32 if( t1<=t[l] ) dp[l][r][0]=min(dp[l][r][0],t1); 33 34 35 ///dp[l][r][1]; 36 int t2=dp[l][r-1][1]+(pos[r]-pos[r-1]); 37 if( t2<=t[r] ) dp[l][r][1]=min(dp[l][r][1],t2); 38 t2=dp[l][r-1][0]+(pos[r]-pos[l]); 39 if( t2<=t[r] ) dp[l][r][1]=min(dp[l][r][1],t2); 40 } 41 } 42 int ans=min(dp[1][n][0],dp[1][n][1]); 43 if( ans==inf ) printf("-1 "); 44 else printf("%d ",ans); 45 return 0; 46 }