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
");
			continue;
		}
		ans = 0;
		dfs(0, 0);
		printf("%d
", ans);
	}
	return 0;
}