POJ 1967 - Alibaba

http://poj.org/problem?id=1967

概要

一直線上に \(n\) 個の宝があり、宝の位置と宝が消えてしまう時刻が与えられる。 アリババは単位距離を単位時間で移動でき、宝を取るのに時間はかからないとする。

適当な位置からスタートし、宝をすべて取れるかどうかを答える。 また宝をすべて取れる場合、それに必要な最短の時間を答える。

制約

解法

DP。このような種類の DP を区間 DP というらしい(?)。

まずスタート位置は最短時間を達成するにはいずれかの宝の位置となる。

また、既に通ったことがある区間が [i, j] のとき、次の移動先 k はこの区間に含まれない。 なぜなら、もし k に移動することで新たに宝を取れるとすると、既にその場所は通ったことがあるのでその時点で取ったほうが良いからである。 よって、最適に移動したときの経路は徐々に振れ幅が大きくなるジグザグのような形になる。

開区間 [i, j] を通ったことがあり、現在左端 (位置 i) にいるときの最短時間を dpL[i][j]、現在右端にいるときの最短時間を dpR[i][j] とすると、

dpL[i][i] = dpR[i][i] = 0
dpL[i][j] = min(dpL[i+1][j] + (i+1 から i の距離), dpR[i+1][j] + (j から i の距離)) (宝が消えてない場合)
dpR[i][j] = min(dpR[i][j-1] + (j-1 から j の距離), dpL[i][j-1] + (i から j の距離)) (宝が消えてない場合)

という漸化式が成り立つ。

これだと時間計算量・空間計算量ともに \(O(n ^ 2)\) になる。 Time Limit が 5000MS なので定数倍最適化をちょっとやると間に合う。 またこの DP は高々1つ前の結果しか使わないので、DP 表をそれぞれ2つ持つだけで計算できるので空間計算量を \(O(n)\) にすることができる。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   while (scanf("%d", &N) != EOF) {
 9     static const int MAXN = 10000;
10     static const int INF = 100000000;
11     static pair<int,int> a[MAXN];
12     for (int i = 0; i < N; i++) {
13       scanf("%d %d", &a[i].first, &a[i].second);
14     }
15     static int dpL[MAXN], dpR[MAXN];
16     for (int i = N-1; i >= 0; i--) {
17       static int prevL[MAXN], prevR[MAXN];
18       fill_n(dpL, N, INF);
19       fill_n(dpR, N, INF);
20       dpL[i] = dpR[i] = 0;
21       for (int j = i+1; j < N; j++) {
22         if (i+1 < N) {
23           const int x = min(prevL[j] + a[i+1].first - a[i].first, prevR[j] + a[j].first - a[i].first);
24           if (x < a[i].second) {
25             dpL[j] = x;
26           }
27           dpL[j] = min(dpL[j], INF);
28         }
29         if (j > 0) {
30           const int x = min(dpR[j-1] + a[j].first - a[j-1].first, dpL[j-1] + a[j].first - a[i].first);
31           if (x < a[j].second) {
32             dpR[j] = x;
33           }
34           dpR[j] = min(dpR[j], INF);
35         }
36       }
37       copy(dpL+i, dpL+N, prevL+i);
38       copy(dpR+i, dpR+N, prevR+i);
39     }
40     const int ans = min(dpL[N-1], dpR[N-1]);
41     if (ans >= INF) {
42       puts("No solution");
43     } else {
44       printf("%d\n", ans);
45     }
46   }
47   return 0;
48 }
poj/1967.cc