思路：

离散化之后dp，dp[i][j]表示完成前i个任务并且处在第j个点所需要的最小代价。

实现：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 pair<int, int> a[1005];
 4 int dp[1005][4005];
 5 int main()
 6 {
 7     ios::sync_with_stdio(false);
 8     int T, n; cin >> T;
 9     while (T--)
10     {
11         cin >> n;
12         vector<int> v;
13         for (int i = 1; i <= n; i++)
14         {
15             cin >> a[i].first >> a[i].second;
16             v.push_back(a[i].first);
17             v.push_back(a[i].second);
18             if (a[i].first < a[i].second - 1)
19             {
20                 v.push_back(a[i].first + 1);
21                 v.push_back(a[i].second - 1);
22             }
23         }
24         sort(v.begin(), v.end());
25         v.erase(unique(v.begin(), v.end()), v.end());
26         int m = v.size();
27         for (int i = 1; i <= n; i++)
28         {
29             a[i].first = lower_bound(v.begin(), v.end(), a[i].first) - v.begin();
30             a[i].second = lower_bound(v.begin(), v.end(), a[i].second) - v.begin();
31         }
32         for (int i = 0; i < m; i++) dp[0][i] = 0;
33         for (int i = 1; i <= n; i++)
34         {
35             int l = a[i].first, r = a[i].second;
36             for (int j = l; j <= r; j++) dp[i][j] = dp[i - 1][j];
37             for (int j = 0; j < l; j++)
38             {
39                 dp[i][j] = dp[i][l] + (abs(v[j] - v[l]) + 1 >> 1);
40                 if (l < r) dp[i][j] = min(dp[i][j], dp[i][l + 1] + (abs(v[j] - v[l + 1]) + 1 >> 1));
41             }
42             for (int j = r + 1; j < m; j++)
43             {
44                 dp[i][j] = dp[i][r] + (abs(v[j] - v[r] + 1) >> 1);
45                 if (l < r) dp[i][j] = min(dp[i][j], dp[i][r - 1] + (abs(v[j] - v[r - 1]) + 1 >> 1));
46             }
47         }
48         cout << *min_element(dp[n], dp[n] + m) << endl;
49     }
50     return 0;
51 }