1044.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1044 on 2006-01-06 at 22:12:58 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 8;
const int LIMIT = 32;

class Stop {
public:
	int s, d, p;
	int pay;
	void make();
	bool contain(int) const;
	bool operator <(const Stop&) const;
};
void Stop::make() {
	scanf("%d %d %d", &s, &d, &p);
	pay = (d - s) * p;
}
bool Stop::contain(int m) const {
	return (m >= s && m < d);
}
bool Stop::operator <(const Stop& st) const {
	return pay > st.pay;
}

Stop stop[LIMIT];
int con[MAX], sum[LIMIT], cost;
int ton, n, b;

void DFS(int, int);

int main()
{
	int i;

	while(scanf("%d %d %d", &n, &b, &ton) != EOF && n != 0) {
		memset(con, 0, sizeof(con)); memset(sum, 0, sizeof(sum));
		cost = 0;
		for(i = 0; i < ton; i++) stop[i].make();
		sort(stop, stop+ton);
		for(i = ton-1; i >= 0; i--) sum[i] = sum[i+1]+stop[i].pay;
		DFS(0, 0);
		printf("%d\n", cost);
	}
	
	return 0;
}

void DFS(int o, int total)
{
	int i, j;
	cost = max(cost, total);
	for(j = o; j < ton; j++) {
		bool can = true;
		for(i = stop[j].s; i < stop[j].d; i++) {
			con[i] += stop[j].p;
			if(con[i] > n) can = false;
		}
		if(can && total+sum[j] > cost) DFS(j+1, total+stop[j].pay);
		for(i = stop[j].s; i < stop[j].d; i++) con[i] -= stop[j].p;
	}
}