1388.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1388 on 2006-01-10 at 16:59:33 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 256;
const int N_MAX = 20;
const int LIMIT = 1024;
const int INF = 200000000;

int main()
{
	int n, T, price[N_MAX+1][N_MAX*LIMIT];
	int i, j, k, t, case_no;

	for(case_no = 0; scanf("%d", &n) != EOF; case_no++) {
		if(case_no != 0) putchar('\n');
		for(i = 0; i <= N_MAX; i++)
			for(j = 0; j < N_MAX*LIMIT; j++) price[i][j] = INF;
		price[0][0] = 0;
		for(i = 0; i < n; i++) {
			int w, p;
			scanf("%d %d", &w, &p);
			for(j = min(N_MAX, i+1); j > 0; j--) {
				int l = j * LIMIT;
				for(k = w; k < l; k++)
					price[j][k] = min(price[j-1][k-w]+p, price[j][k]);
			}
		}
		scanf("%d", &T);
		for(t = 0; t < T; t++) {
			int m, l, r;
			scanf("%d %d %d", &m, &l, &r);
			l *= m, r *= m;
			int p = INF;
			for(i = l; i <= r; i++) p = min(p, price[m][i]);
			if(p == INF) printf("impossible\n");
			else printf("%d\n", p);
		}
	}
	
	return 0;
}