uva 301 Transportation 铁路公司的阳谋 纯dfs暴力

题目比较难理解。

给出铁路的容量和站点数，以及几笔订单，要求算出如何盈利最大。

咋一看想贪心，但无法确定是最优解啊。

于是用dfs做，就两种状况，选与不选，先开一个每个站点的当前人数数组，假设要选，然后各个站点加上人数判断会不会超人数，不会就进入选择的下一轮dfs，然后把人数减掉，进入不选的dfs。

这题据说用数组标记会超时。。。

代码：

#include    
  
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;  
}