2216.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2216 on 2006-04-26 at 12:27:22 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int WN = 128;
const int INF = 1 << 30;

int n, m, pt[WN][2];

bool finish(int);

int main()
{
	int t, T, i;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d", &n, &m);
		for(i = 0; i < n; i++) scanf("%d %d", &pt[i][0], &pt[i][1]);
		int l = 0, h = (pt[0][0]+pt[0][1])*m;
		while(h != l) {
			int mid = (h + l) / 2;
			if(finish(mid)) h = mid;
			else l = mid+1;
		}
		printf("%d\n", h);
	}
	
	return 0;
}

bool finish(int cost)
{
	int fb[WN] = { 0 }, i, j, k;
	for(i = 1; i <= m; i++) fb[i] = -INF;
	for(i = 0; i < n; i++) {
		int lmt = cost/pt[i][0], nxt[WN];
		memcpy(nxt, fb, sizeof(fb));
		for(j = 0; j <= lmt; j++) {
			for(k = 0; k <= m; k++) {
				int bn = (cost-j*pt[i][0])/pt[i][1];
				if(k >= j) nxt[k] = max(nxt[k], fb[k-j]+bn);
			}
			if(nxt[m] >= m) return true;
		}
		memcpy(fb, nxt, sizeof(nxt));
	}
	return false;
}