題目： UVa - 10337 - Flight Planner

題目說明

在一個平面座標系上，有一架飛機從原點 ( 0, 0 ) 起飛，要到 X ( X, 0 )，將原點到 X 每 100 miles 分為一段，給每段的各個空層 ( 共 9 層 ) 的風速，飛機每飛過 100 miles 可以選擇往上一層、往下一層、或是平飛，花費的燃料依序為 60、20、30，且花費的燃料還要減掉該層的風速，求從起點到終點花費的最少燃料為何。飛機不能在地面平飛 ( 第 0 層 )，也不能飛超過第 9 層。

Input： 第一個整數 T，表示有 T 組測資，每組測資第一個整數為 X，後面 9 * X / 100 的表格為風速，以左下角為原點，向右為 x 軸 ( 0 ~ X / 100 )，向上為 y 軸 ( 0 ~ 9 )。

Output： 輸出從起點到終點的最小花費燃料。

解題思路

動態規劃題，先讀取測資，將每 100 miles 分為一段，winds[i][j] 表第 i 段，第 j 層的風速，先讀取風速，記得是從第 9 層開始。

定義 dp[i][j] 表飛機到達第 i 段，第 j 層所需的最小花費，對於 (i, j) 來說，只能從 (i - 1, j)、(i - 1, j - 1)、(i - 1, j + 1) 到達，依此想法做動態規劃即可，記得注意題目要求的一些限制，如不能在第 0 層走等等。

參考解法

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
#include <bits/stdc++.h>

using namespace std;

// reference: https://ppt.cc/fzYlzx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

const int inf = (int)1e9;

int T;
int X;
int winds[1005][10]; // winds[i][j] 表第 i 段，第 j 層的風速
int dp[1005][10];    // dp[i][j] 表飛機到達第 i 段，第 j 層所需的最小花費

void read()
{
    cin >> X;
    X /= 100;

    for (int i = 9; i >= 0; --i) for (int j = 0; j < X; ++j)
        cin >> winds[j][i], dp[j][i] = inf;
}

void solve()
{
    dp[0][0] = 0; // 起點

    for (int i = 1; i <= X; ++i) for (int j = 0; j < 10; ++j)
    {
        int mn = INT_MAX;
        if (j > 0)
        {
            mn = min(dp[i - 1][j] + 30 - winds[i - 1][j], mn);         // 從 i - 1 平飛到 i
            mn = min(dp[i - 1][j - 1] + 60 - winds[i - 1][j - 1], mn); // 從 i - 1 向上飛到 i
        }
        if (j < 9) mn = min(dp[i - 1][j + 1] + 20 - winds[i - 1][j + 1], mn); // 從 i - 1 向下飛到 i
        dp[i][j] = mn;
    }

    cout << dp[X][0] << "\n\n";
}

int main()
{
    cin >> T;
    while (T--)
    {
        read();
        solve();
    }
}

參考資料

[UVA] 10337 - Flight Planner | 水泥城式