2252.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2252 on 2006-05-29 at 10:21:43 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int HPM = 1024;
const int N = 8;
const int HN = 128;
const int INF = 1 << 28;

int main()
{
	int t, T, i, j, k;
	int h[N], m[N], hit[HN], hp[HN][HPM];

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		int n, hn, hpm; scanf("%d", &n);
		for(i = 0; i < n; i++) scanf("%d %d", &m[i], &h[i]);
		h[n] = m[n] = 0; n++;
		scanf("%d %d", &hpm, &hn);
		for(i = 0; i < hn; i++) scanf("%d", &hit[i]);
		for(i = 0; i < hpm; i++) hp[0][i] = INF;
		hp[0][hpm] = 0;
		for(k = 0; k < hn; k++) {
			for(i = 0; i <= hpm; i++) hp[k+1][i] = INF;
			for(i = hit[k]+1; i <= hpm; i++)
				for(j = 0; j < n; j++) {
					int thp = min(hpm, i-hit[k]+h[j]);
					hp[k+1][thp] = min(hp[k+1][thp], hp[k][i]+m[j]);
				}
		}
		int best = INF;
		for(i = 1; i <= hpm; i++) best = min(best, hp[hn][i]);
		if(best == INF) printf("Lose the friend.\n");
		else printf("%d\n", best);
	}
	
	return 0;
}