2358.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 2358 on 2006-09-14 at 17:10:13 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int BN = 512;
const int HN = 42000;

class Box {
public:
	int cnt, hlmt, h;
	void make() { scanf("%d %d %d", &h, &hlmt, &cnt); }
	bool operator <(const Box& b) const { return hlmt < b.hlmt; }
};

int main()
{
	int n, stack[HN];
	Box b[BN];
	bool vst[HN];
	
	while(scanf("%d", &n) != EOF) {
		for(int i = 0; i < n; i++) b[i].make();
		sort(b, b+n);
		memset(vst, false, sizeof(vst)); vst[0] = true;
		int top = 0, best = 0; stack[top++] = 0;
		for(int i = 0; i < n; i++)
			for(int k = 0; k < b[i].cnt; k++)
				for(int j = top-1; j >= 0; j--) {
					int h = stack[j]+b[i].h;
					if(h > b[i].hlmt || vst[h]) continue;
					vst[h] = true; stack[top++] = h;
					best >?= h;
				}
		printf("%d\n", best);
	}
	
	return 0;
}