UVA 757 Gone Fishing：貪心 + 模擬最大化捕魚量

題目大意

John 有 h 小時（換算為 5 分鐘間隔數）去釣魚，n（≤25）個魚塘沿單向路排列。每塘初始產量 fᵢ，每 5 分鐘遞減 dᵢ。移動到下一塘需 tᵢ 個間隔。求最大期望捕魚數，並輸出各塘停留時間（若多解，優先在前塘多待）。

解題思路

1. 預處理前綴和 travel[i] = 從第 1 塘到第 i 塘的移動時間。
2. 枚舉最後停留的塘 k（1~n），可用釣魚時間 T = h×12 - travel[k]。
3. 在前 k 塘中貪心分配時間：每次選擇當前產量最高的塘釣 5 分鐘，更新該塘產量 max(0, f - d)，直到時間用盡或所有塘產量歸零。
4. 若時間剩餘且無魚可釣，全部加給第 1 塘（符合多解優先規則）。
5. 記錄最大總魚數對應的分配方案。

代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, h, f[30], d[30], t[30], ans, rec[30], recA[30], tmp[30];

int findBest(int k) { // 在前 k 個塘找當前魚最多的
    int best = 0, id = -1;
    for (int i = 0; i <= k; ++i)
        if (tmp[i] > best) { best = tmp[i]; id = i; }
    return id;
}

int main() {
    bool firstCase = true;
    while (scanf("%d", &n) == 1 && n) {
        if (!firstCase) puts(""); firstCase = false;
        int H; scanf("%d", &H); h = H * 12;
        for (int i = 0; i < n; ++i) scanf("%d", &f[i]);
        for (int i = 0; i < n; ++i) scanf("%d", &d[i]);
        t[0] = 0;
        for (int i = 1; i < n; ++i) { scanf("%d", &t[i]); t[i] += t[i-1]; }

        memset(recA, 0, sizeof(recA)); ans = 0;
        for (int k = 0; k < n; ++k) {
            int time = h - t[k]; if (time <= 0) break;
            memcpy(tmp, f, sizeof(f));
            memset(rec, 0, sizeof(rec));
            int sum = 0;
            while (time--) {
                int id = findBest(k);
                if (id == -1) break;
                sum += tmp[id];
                tmp[id] = max(0, tmp[id] - d[id]);
                ++rec[id];
            }
            if (time > 0) rec[0] += time; // 剩餘時間給第一塘
            if (sum > ans) { ans = sum; memcpy(recA, rec, sizeof(rec)); }
        }

        printf("%d", recA[0] * 5);
        for (int i = 1; i < n; ++i) printf(", %d", recA[i] * 5);
        printf("\nNumber of fish expected: %d\n", ans);
    }
    return 0;
}

關鍵點

• 時間單位統一為 5 分鐘間隔。
• 貪心選擇當前最大產量塘，符合「單調遞減」特性，證明可行。
• 多解處理：枚舉 k 時從小到大，同 k 內剩餘時間給第 1 塘，自然滿足「盡可能在前塘多待」。
• 輸出格式：逗號分隔，最後一行空行分隔測資。

複雜度

• 枚舉 k：O(n)；每次模擬 O(h × n)，h ≤ 16×12=192，總計 O(n²h) 極小。
• 空間：O(n)