设$dp[l][r][p]$为走完区间$[l,r]$，在端点$p$时所需的最短时间（$p=0$代表在左端点，$p=1$代表在右端点）
根据题意显然有状态转移方程$\left\{\begin{matrix}dp[l][r][0]=min(dp[l+1][r][0]+x[l+1]-x[l],dp[l+1][r][1]+x[r]-x[l]);\\ dp[l][r][1]=min(dp[l][r-1][0]+x[r]-x[l],dp[l][r-1][1]+x[r]-x[r-1]);\end{matrix}\right.$
复杂度是$O(n^2)$的，对于10000的数据量还是有些勉强，因此某些常数比较大的算法会T掉。
为此我测试了多种不同的算法，比较了一下它们各自的优劣。
首先是最普通的区间dp：(440ms)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+,inf=0x3f3f3f3f;
int dp[N][N][],n,x[N],t[N],ans; int main() {
while(scanf("%d",&n)==) {
for(int i=; i<n; ++i)scanf("%d%d",&x[i],&t[i]);
for(int i=; i<n; ++i)dp[i][i][]=dp[i][i][]=;
for(int l=n-; l>=; --l)
for(int r=l+; r<n; ++r) {
dp[l][r][]=min(dp[l+][r][]+x[l+]-x[l],dp[l+][r][]+x[r]-x[l]);
dp[l][r][]=min(dp[l][r-][]+x[r]-x[l],dp[l][r-][]+x[r]-x[r-]);
if(dp[l][r][]>=t[l])dp[l][r][]=inf;
if(dp[l][r][]>=t[r])dp[l][r][]=inf;
}
int ans=min(dp[][n-][],dp[][n-][]);
if(ans==inf)printf("No solution\n");
else printf("%d\n",ans);
}
return ;
}
注意l要从右往左循环就行。
然后是用滚动数组优化后的dp：(290ms)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+,inf=0x3f3f3f3f;
int dp[][N][],n,x[N],t[N],ans; int main() {
while(scanf("%d",&n)==) {
for(int i=; i<n; ++i)scanf("%d%d",&x[i],&t[i]);
memset(dp,,sizeof dp);
for(int l=n-; l>=; --l)
for(int r=l+; r<n; ++r) {
dp[l&][r][]=min(dp[l&^][r][]+x[l+]-x[l],dp[l&^][r][]+x[r]-x[l]);
dp[l&][r][]=min(dp[l&][r-][]+x[r]-x[l],dp[l&][r-][]+x[r]-x[r-]);
if(dp[l&][r][]>=t[l])dp[l&][r][]=inf;
if(dp[l&][r][]>=t[r])dp[l&][r][]=inf;
}
int ans=min(dp[][n-][],dp[][n-][]);
if(ans==inf)printf("No solution\n");
else printf("%d\n",ans);
}
return ;
}
和上面的代码唯一的不同之处就是l换成了l&1，l+1换成了l&1^1。
其他算法：
bfs刷表法：(1940ms)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+,inf=0x3f3f3f3f;
int dp[][N][],vis[][N][],n,x[N],t[N],ans,ka;
struct D {int l,r,p;};
queue<D> q; void upd(int l,int r,int p,int ad) {
if(vis[l&][r][p]!=l)vis[l&][r][p]=l,dp[l&][r][p]=inf,q.push({l,r,p});
if(dp[l&][r][p]>ad)dp[l&][r][p]=ad;
} int bfs() {
memset(vis,-,sizeof vis);
int ret=inf;
while(!q.empty())q.pop();
for(int i=; i<n; ++i)upd(i,i,,);
while(!q.empty()) {
int l=q.front().l,r=q.front().r,p=q.front().p;
q.pop();
if(l==&&r==n-) {ret=min(ret,dp[l&][r][p]); continue;}
int P=p==?l:r;
if(l>&&dp[l&][r][p]+x[P]-x[l-]<t[l-])upd(l-,r,,dp[l&][r][p]+x[P]-x[l-]);
if(r<n-&&dp[l&][r][p]+x[r+]-x[P]<t[r+])upd(l,r+,,dp[l&][r][p]+x[r+]-x[P]);
}
return ret;
} int main() {
while(scanf("%d",&n)==) {
++ka;
for(int i=; i<n; ++i)scanf("%d%d",&x[i],&t[i]);
int ans=bfs();
if(ans==inf)printf("No solution\n");
else printf("%d\n",ans);
}
return ;
}
这个算法对于本题来说常数比较大，必须要用滚动数组优化。
dfs记忆化搜索法：(1580ms)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+,inf=0x3f3f3f3f;
int dp[N][N][],vis[N][N],n,x[N],t[N],ans,ka; void dfs(int l,int r) {
if(vis[l][r]==ka)return;
vis[l][r]=ka;
if(l==r)dp[l][r][]=dp[l][r][]=;
else {
dfs(l+,r),dfs(l,r-);
dp[l][r][]=min(dp[l+][r][]+x[l+]-x[l],dp[l+][r][]+x[r]-x[l]);
dp[l][r][]=min(dp[l][r-][]+x[r]-x[l],dp[l][r-][]+x[r]-x[r-]);
if(dp[l][r][]>=t[l])dp[l][r][]=inf;
if(dp[l][r][]>=t[r])dp[l][r][]=inf;
}
} int main() {
while(scanf("%d",&n)==) {
++ka;
for(int i=; i<n; ++i)scanf("%d%d",&x[i],&t[i]);
dfs(,n-);
int ans=min(dp[][n-][],dp[][n-][]);
if(ans==inf)printf("No solution\n");
else printf("%d\n",ans);
}
return ;
}
这个算法常数也比较大，但无法用滚动数组来优化，因此需要额外增设一个vis数组和一个变量ka，来避免dp数组的初始化。
去掉一维直接dp法：(260ms)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+,inf=0x3f3f3f3f;
int dp[N][],n,x[N],t[N],ans; int main() {
while(scanf("%d",&n)==) {
for(int i=; i<n; ++i)scanf("%d%d",&x[i],&t[i]);
memset(dp,,sizeof dp);
for(int i=; i<n; ++i)
for(int l=; l+i<n; ++l) {
dp[l][]=min(dp[l][]+x[l+i]-x[l],dp[l][]+x[l+i]-x[l+i-]);
dp[l][]=min(dp[l+][]+x[l+]-x[l],dp[l+][]+x[l+i]-x[l]);
if(dp[l][]>=t[l])dp[l][]=inf;
if(dp[l][]>=t[l+i])dp[l][]=inf;
}
int ans=min(dp[][],dp[][]);
if(ans==inf)printf("No solution\n");
else printf("%d\n",ans);
}
return ;
}
这个算法无论是时间还是空间的消耗都是最小的，虽然比较抽象。设dp[i][l][p]为区间左端点为l，长度为i+1，当前位置为p时所需的最短时间，则第一维i可以直接去掉。