以下两种递推方式仅仅只有方向的不同然而时间上却有巨大的差异，一个直接t另一个0.62s 0.62s代码

#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<iostream>
const int N=1e4+5;
int f[N][N][2],d[N],t[N];
int n;
int read(){
    char ch=getchar();int f=1,t=0;
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
    return t*f;
}

signed main(){
    //ios::sync_with_stdio(0);cin.tie(0);
    //freopen("1.out","w",stdout);
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++)d[i]=read(),t[i]=read();
        for(int i=1;i<=n;i++)f[i][i][0]=f[i][i][1]=0;
        for(int i=n-1;i>=1;i--){
            for(int j=i+1;j<=n;j++){
                f[i][j][0]=std::min(f[i+1][j][0]+d[i+1]-d[i],f[i+1][j][1]+d[j]-d[i]);
                f[i][j][1]=std::min(f[i][j-1][0]+d[j]-d[i],f[i][j-1][1]+d[j]-d[j-1]);
                if(f[i][j][0]>=t[i])f[i][j][0]=100000000;
                if(f[i][j][1]>=t[j])f[i][j][1]=100000000;
            }
        }
        int ans=std::min(f[1][n][0],f[1][n][1]);
        if(ans<100000000)printf("%d\n",ans);
        else printf("No solution\n");
    }
    return 0;
}

超时代码

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<map>
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e4+5;
int f[N][N][2],d[N],t[N];
int n;
int read(){
    char ch=getchar();int f=1,t=0;
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
    return t*f;
}

int _min(int x,int y){
    if(x>y)return y;
    else return x;
}

signed main(){
    //ios::sync_with_stdio(0);cin.tie(0);
    //freopen("1.out","w",stdout);
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++)d[i]=read(),t[i]=read();
        for(int i=1;i<=n;i++)f[i][i][0]=f[i][i][1]=0;
        for(int j=2;j<=n;j++){
            for(int i=j-1;i>=1;i--){
                f[i][j][0]=_min(f[i+1][j][0]+d[i+1]-d[i],f[i+1][j][1]+d[j]-d[i]);
                f[i][j][1]=_min(f[i][j-1][0]+d[j]-d[i],f[i][j-1][1]+d[j]-d[j-1]);
                if(f[i][j][0]>=t[i])f[i][j][0]=INF;
                if(f[i][j][1]>=t[j])f[i][j][1]=INF;
            }
        }
        int ans =_min(f[1][n][0],f[1][n][1]);
        if(ans==INF)printf("No solution\n");
        else printf("%d\n",ans);
    }
    return 0;
}