题意分析

该问题描述的是阿里巴巴需要在一条直线上收集多个宝藏，每个宝藏有特定的位置和消失时间。要求找出一个最优的收集顺序，使得阿里巴巴能够在所有宝藏消失前收集完所有宝藏，并且总时间最短。如果无法满足所有宝藏的时间限制，则输出"No solution"。

1.宝藏位置：

每个宝藏位于直线上不同的位置，按位置递增给出。

2.时间限制：

每个宝藏有一个消失时间，必须在到达该位置时不超过这个时间。

3.收集时间：

收集宝藏的时间可以忽略不计，但移动需要时间。

解题思路

该问题可以使用动态规划来解决 状态定义为：$dp[i][j][0]$：表示收集完从第i到第j个宝藏，且当前位于第i个宝藏时的最小时间。 $dp[i][j][1]$：表示收集完从第i到第j个宝藏，且当前位于第j个宝藏时的最小时间。

状态转移 1.从$dp[i][j][0]$转移： 可以从$dp[i+1][j][0]$转移过来，即从$i+1$向左走到$i$。也可以从$dp[i+1][j][1]$转移过来，即从$j$向左走到$i$。转移时需要加上移动时间，并检查是否超过宝藏$i$的消失时间。 2.从$dp[i][j][1]$转移： 可以从$dp[i][j-1][1]$转移过来，即从$j-1$向右走到$j$。也可以从$dp[i][j-1][0]$转移过来，即从$i$向右走到$j$。转移时需要加上移动时间，并检查是否超过宝藏j的消失时间。

初始化和边界条件 初始化时，单个宝藏的收集时间为0。如果转移后的时间超过宝藏的消失时间，则将该状态设为不可达$INF$。

最终答案 最终的答案为$min(dp[1][n][0], dp[1][n][1])$，即从第一个到第$n$个宝藏，且位于最左或最右时的最小时间。如果该值仍为$INF$，则输出"No solution"。

代码实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int N =  1e4;
const int INF = 0x3f3f3f3f;
 
int n,a[N+10],b[N+10],f[2][N+10][2];
 
main(){
    //freopen("F:\\rush.txt","r",stdin);
    while (~scanf("%lld",&n)){
        for (int i = 1;i <= n;i++)
            scanf("%lld%lld",&a[i],&b[i]);
        for (int i = 1;i <= n;i++){
            f[1][i][0] = f[1][i][1] = (b[i]>0?0:INF);
        }
        for (int i = 1;i <= n-1;i++){
            int cur = i&1;
            memset(f[cur^1],INF,sizeof f[cur^1]);
            for (int j = 1;j <= n-i+1;j++){
                if (f[cur][j][0]<INF){
                    // l = j,r = j+i-1,0
                    // l = j-1,r = j-1+i+1-1 = j+i-1
                    if (j >= 2){
                        f[cur^1][j-1][0] = min(f[cur^1][j-1][0],f[cur][j][0]+a[j]-a[j-1]);
                        if (f[cur^1][j-1][0]>=b[j-1])
                            f[cur^1][j-1][0] = INF;
                    }
                    //l = j,r = j+i+1-1 = j+i
                    if (j+i<=n){
                        f[cur^1][j][1] = min(f[cur^1][j][1],f[cur][j][0]+a[j+i]-a[j]);
                        if (f[cur^1][j][1] >= b[j+i])
                            f[cur^1][j][1] = INF;
                    }
                }
                if (f[cur][j][1]<INF){
                    // l = j,r = j+i-1,1
                    // l = j-1,r = j-1+i+1-1 = j+i-1
                    if (j >= 2){
                        f[cur^1][j-1][0] = min(f[cur^1][j-1][0],f[cur][j][1]+a[j+i-1]-a[j-1]);
                        if (f[cur^1][j-1][0]>=b[j-1])
                            f[cur^1][j-1][0] = INF;
                    }
                    //l = j,r = j+i+1-1 = j+i
                    if (j+i<=n){
                        f[cur^1][j][1] = min(f[cur^1][j][1],f[cur][j][1]+a[j+i]-a[j+i-1]);
                        if (f[cur^1][j][1] >= b[j+i])
                            f[cur^1][j][1] = INF;
                    }
                }
            }
        }
        int ans = min(f[n&1][1][0],f[n&1][1][1]);
        if (ans>=INF)
            puts("No solution");
        else
            printf("%lld\n",ans);
    }
    return 0;
}