解題區/解題區 - UVa

UVa 801 - Flight Planning

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給予飛機在平流層飛行資訊，在每一種高度下維持飛行的耗油量成線性關係，以及每一段飛行旅程上的平流層的風速為何，藉由線性內插得到在某高度下的飛行速度，忽略在轉換高度時的耗油量，問從起點到終點的最少耗油量為何 (無條件進位)。

Sample Input

1
2
3
4
5
6
7
8
2
2
1500 -50 50
1000 0 0
3
1000 50 0
2000 0 20
1800 50 100

Sample Output

1
2
Flight 1: 35 30 13986
Flight 2: 20 30 30 23502

Solution

單源最短路徑，只是每一點要使用 $20$ 個狀態維護抵達那一層時在哪一種高度下飛行。必須窮舉轉移到下一層的所有高度，因為有可能飛行慢而增加耗油時間。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Leg {
    double mile, f20, f40;
} legs[1024];
const double VCRUISE = 400;
const double AOPT = 30000;
const double GPHOPT = 2000;
const double GPHEXTRA = 10;
const double CLIMBCOST = 50;
const int MAXN = 1024;	// maximum #legs
const int MAXH = 45;	// between 20,000 and 40,000 feet
const double DINF = 1e+20;
double inter(Leg a, double h) {
    return a.f20 + (a.f40 - a.f20) * (h - 20000) / (40000 - 20000);
}
void solve(int n) {
    double dp[MAXN][MAXH];
    int from[MAXN][MAXH];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= 40; j++)
            dp[i][j] = DINF;
    }
    
    dp[0][0] = 0;	// leg 0: altitude 0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= 40; j++) {
            if (dp[i][j] >= DINF)
                continue;
            double alti_a = j * 1000.f;
            for (int k = 20; k <= 40; k++) {
                double cc = 0, alti_b;
                alti_b = k * 1000.f;
                
                if (alti_b > alti_a)
                    cc += CLIMBCOST * (alti_b - alti_a) / 1000.f;
                double v = VCRUISE + inter(legs[i+1], alti_b);
                if (v <= 0)
                	continue;
                double c = fabs(alti_b - AOPT) * GPHEXTRA / 1000.f + GPHOPT;
                cc += c * legs[i+1].mile / v;
                if (dp[i][j] + cc < dp[i+1][k])
                    dp[i+1][k] = dp[i][j] + cc, from[i+1][k] = j;
            }
        }
    }
    
    double ret = DINF;
    int last = -1;
    vector<int> solution;
    for (int i = 20; i <= 40; i++) {
        if (dp[n][i] < ret)
            ret = dp[n][i], last = i;
    }
    for (int i = n; i > 0; i--) {
        solution.push_back(last);
        last = from[i][last];
    }
    for (int i = n-1; i >= 0; i--)
        printf(" %d", solution[i]);
    // tricky 
    printf(" %.0lf\n", ceil(ret));
}
int main() {
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lf %lf %lf",
                  &legs[i].mile, &legs[i].f20, &legs[i].f40);
        }
        printf("Flight %d:", ++cases);
        solve(n);
    }
    return 0;
}