UVA 812 Trade on Verweggistan：暴力 DFS 求最大利潤與前 10 購買方案

問題描述

有 w 種貨物，第 i 種有 b_i 個價格序列。商人必須從第一個開始連續購買（即若買第 k 個，則前 k-1 個必須全買）。每種貨物選擇一個前綴購買，利潤為該前綴價格和（題目給的是「成本」，利潤 = 10 - 成本）。求總最大利潤，及能達成最大利潤的購買總件數（前 10 小）。

解法：獨立選擇 + DFS 組合

1. 對每種貨物，計算前綴和，找出最大前綴和 Max_i 及所有達成該值的購買件數 choices[i]（包含 0 件）。
2. 總最大利潤 ans = Σ Max_i。
3. 用 DFS 遍歷所有貨物的選擇組合，累加總件數，標記 possible[sum] = true。
4. 輸出前 10 個 possible[x] == true 的 x。

關鍵代碼

int arr[55][55], sum[55][55];
vector choices[55];
bool possible[55*55];

void dfs(int idx, int total) {
    if (idx == w) { possible[total] = true; return; }
    for (int c : choices[idx]) dfs(idx + 1, total + c);
}

int main() {
    int w, caseNo = 1;
    while (scanf("%d", &w) == 1 && w) {
        for (int i = 0; i < w; i++) {
            int b; scanf("%d", &b);
            for (int j = 0; j < b; j++) {
                scanf("%d", &arr[i][j]);
                arr[i][j] = 10 - arr[i][j]; // 利潤
                sum[i][j] = (j?sum[i][j-1]:0) + arr[i][j];
            }
            int mx = 0; choices[i].clear(); choices[i].push_back(0);
            for (int j = 0; j < b; j++) {
                if (sum[i][j] > mx) { mx = sum[i][j]; choices[i].clear(); choices[i].push_back(j+1); }
                else if (sum[i][j] == mx) choices[i].push_back(j+1);
            }
            ans += mx;
        }
        memset(possible, 0, sizeof(possible));
        dfs(0, 0);
        // 輸出
    }
}

複雜度

• w ≤ 10, b ≤ 10，狀態數極小，DFS 瞬間完成。
• 總件數上限 100，possible 數組 10000 足夠。

總結

本題利用了「各貨物選擇獨立」的性質，先單獨求各貨物最優前綴，再組合枚舉總件數。暴力 DFS 完全可行，體現了「分治 + 組合」的思想。注意輸出格式：案例編號、空行分隔、前 10 個數字前加空格。