uva 301 Transportation 鐵路公司的陽謀 純dfs暴力

題目比較難理解。

給出鐵路的容量和站點數，以及幾筆訂單，要求算出如何盈利最大。

咋一看想貪心，但無法確定是最優解啊。

於是用dfs做，就兩種狀況，選與不選，先開一個每個站點的當前人數數組，假設要選，然後各個站點加上人數判斷會不會超人數，不會就進入選擇的下一輪dfs，然後把人數減掉，進入不選的dfs。

這題據說用數組標記會超時。。。

代碼：

#include <cstdio>   
  
const int maxn = 30;  
int cap, num, ord, ans;  
int cnt[10];  
  
struct Order {  
    int s;  
    int e;  
    int p;  
};  
Order o[maxn];  
  
bool judge() {  
    for (int i = 0; i < num; i++)  
        if (cnt[i] > cap)  
            return false;  
    return true;  
}  
  
void dfs(int d, int sum) {  
    if (sum > ans) ans = sum;  
    if (d >= ord) return;  
    for (int i = o[d].s; i < o[d].e; i++)  
        cnt[i] += o[d].p;  
    if (judge())                    //choose   
        dfs(d + 1, sum + o[d].p * (o[d].e - o[d].s));  
    for (int i = o[d].s; i < o[d].e; i++)  
        cnt[i] -= o[d].p;  
    dfs(d + 1, sum);                //not choose   
}  
  
int main() {  
    while (scanf("%d%d%d", &cap, &num, &ord) && (cap || num || ord)) {  
        for (int i = 0; i < num; i++)  
            cnt[i] = 0;  
        for (int i = 0; i < ord; i++)  
            scanf("%d%d%d", &o[i].s, &o[i].e, &o[i].p);  
        if (!cap || !num || !ord) {  
            printf("0\n");  
            continue;  
        }  
        ans = 0;  
        dfs(0, 0);  
        printf("%d\n", ans);  
    }  
    return 0;  
}