UVa 1632 阿里巴巴（区间DP）

题意：

直线上有n个点，其中第i个点的坐标是xi，且它会在di秒之后消失。Alibaba可以从任意位置出发，求访问完所有点的最短时间。

思路：

区间DP。

d[i][j][0]用来表示访问完区间 i ~ j 之间所有点的最短时间，并且此时处于 i 点，相反的，d[i][j][1]表示的是处于 j 点。

 1 #include<iostream> 
 2 #include<string>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 10000 + 5;
 8 const int INF = 10000000;
 9 
10 int a[maxn], b[maxn];
11 int n;
12 int d[maxn][maxn][2];
13 
14 int main()
15 {17     while (cin >> n)
18     {
19         memset(d, 0, sizeof(d));
20         for (int i = 1; i <= n; i++)
21             cin >> a[i] >> b[i];
22         for (int i = n; i >=1; i--)
23         {
24             for (int j = i + 1; j <= n; j++)
25             {
26                 d[i][j][0] = min(d[i + 1][j][0] + a[i + 1] - a[i], d[i + 1][j][1] + a[j] - a[i]);
27                 if (d[i][j][0] >= b[i])    d[i][j][0] = INF;
28                 d[i][j][1] = min(d[i][j-1][1] + a[j] - a[j - 1], d[i][j - 1][0] + a[j] - a[i]);
29                 if (d[i][j][1] >= b[j])    d[i][j][1] = INF;
30             }
31         }
32         int ans = min(d[1][n][0], d[1][n][1]);
33         if (ans == INF) puts("No solution");
34         else printf("%d
", ans);
35     }
36     return 0;
37 }