1215.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1215 on 2006-03-03 at 15:35:03 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 1024;
const int INF = 1 << 30;

int main()
{
	int lost[MAX];
	int i, j, t, T;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		int maxHP, fn; scanf("%d %d", &maxHP, &fn);
		int all = 0, best = INF, lmt = 0;
		lost[0] = 0;
		for(i = 1; i < MAX; i++) lost[i] = INF;
		for(i = 0; i < fn; i++) {
			int hp, score;
			scanf("%d %d", &hp, &score); all += score;
			for(j = lmt; j >= 0; j--)
				if(j+hp >= maxHP) best = min(best, lost[j]+score);
				else { lost[j+hp] = min(lost[j+hp], lost[j]+score); lmt = max(lmt, j+hp); }
		}
		printf("%d\n", max(all-best, 0));
	}
	
	return 0;
}