UVa

UVa00301 UvaLive5516 POJ1040 HDU1456 SCU1031 OpenJ_Bailian1040 Transportation

題目連結 UVa
題目連結 POJ
題目連結 HDU
題目連結 UvaLive
題目連結 SCU
題目連結 OpenJ_Bailian1040

  • 題意：有一列火車從 $A$($0$ 號車站) 開到 $B$($m$ 號車站)，路上經過車站依序編號為 $0$ 到 $m$，現在有 $t$ 筆訂單，每筆訂單有人數，起點和終點，如果接受這筆訂單，就可以獲得人數 $\times$ 經過站數(終點-起點)，火車最多可以載 $n$ 位客人，求最高獲益。
  • 題解：遞迴爆搜，利用前綴和和差分檢查如果加入當前訂單，車上的容量是否足夠。另外需要剪枝，當前的已接受的訂單 + 還沒確定是否要接受的訂單，所有獲益無法成為最佳解即停止搜索。
    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 <algorithm>
    #include <cmath>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <vector>

    using namespace std;
    typedef long long LL;
    struct Data
    {
        int s, t, n, cost;
        bool operator<(const Data &rhs) const { return cost < rhs.cost; }
    };
    int n, b, t;
    int ans;
    vector<int> costSum(25), sum(10);
    vector<Data> v;

    void doit(int d, int dir)
    {
        sum[v[d].s] += dir * v[d].n;
        sum[v[d].t] -= dir * v[d].n;
    }

    bool ok()
    {
        int total = 0;
        for (int i = 0; i <= b; ++i)
        {
            total += sum[i];
            if (total > n)
            {
                return false;
            }
        }
        return true;
    }

    void dfs(int d, int cur)
    {
        // cout << d << ' ' << cur << '\n';
        ans = max(ans, cur);
        if (d == t)
        {
            return;
        }
        if(cur + costSum[d] <= ans)
        {
            return;
        }
        doit(d, 1);
        if (ok())
        {
            dfs(d + 1, cur + (v[d].t - v[d].s) * v[d].n);
        }
        doit(d, -1);
        dfs(d + 1, cur);
        return;
    }

    int main()
    {
        while (cin >> n >> b >> t, n || b || t)
        {
            v.resize(t);
            fill(sum.begin(), sum.end(), 0);
            fill(costSum.begin(), costSum.end(), 0);
            for (int i = 0; i < t; ++i)
            {
                cin >> v[i].s >> v[i].t >> v[i].n;
                v[i].cost = v[i].n * (v[i].t - v[i].s);
            }
            sort(v.begin(), v.end());
            for (int i = t - 1; i >= 0; --i)
            {
                costSum[i] = costSum[i + 1] + v[i].cost;
            }
            ans = 0;
            dfs(0, 0);
            cout << ans << '\n';
        }
    }

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts