2196.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2196 on 2006-04-02 at 22:45:39 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 512;
const int LIMIT = 2560;

class Order {
public:
	int t, pay;
	void make();
};
void Order::make() {
	int a = 0, b = 0;
	scanf("%d %d.%d", &t, &a, &b);
	pay = a * 100 + b;
}

int main()
{
	Order order[MAX];
	int get[LIMIT], t, T, i, j;
	
	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		int n; scanf("%d", &n);
		for(i = 0; i < n; i++) order[i].make();
		int time; scanf("%d", &time);
		memset(get, 0, sizeof(get));
		int best = 0, bt = 0;
		for(i = 0; i < n; i++)
			for(j = time; j >= 0; j--) {
				int ct = j + order[i].t;
				if(ct <= time) {
					get[ct] = max(get[ct], get[j]+order[i].pay);
					if(get[ct] >= best) best = get[ct], bt = ct;
				}
			}
		printf("Problem %d: %d seconds scheduled for $%d.%02d\n", t, bt, best/100, best%100);
	}

	return 0;
}