1770.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1770 on 2006-02-14 at 04:19:07 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 451;

bool vst[MAX*1000], bottle[MAX*10];
int litre, n, dcap, ucap;

bool DFS(int);

int main()
{
	int i, j;

	while(scanf("%d %d", &litre, &n) != EOF) {
		memset(bottle, false, sizeof(bottle)); dcap = 5210; ucap = 0;
		for(i = 0; i < n; i++) {
			int u, d; scanf("%d %d", &d, &u);
			for(j = d; j <= u; j++) bottle[j] = true;
			dcap = min(dcap, d); ucap = max(ucap, u);
		}
		int maxc;
		if(litre >= MAX) maxc = litre;
		else {
			litre *= 1000; memset(vst, false, sizeof(vst));
			for(maxc = litre; !DFS(maxc); maxc--);
		}
		printf("%d\n", litre-maxc);
	}
	
	return 0;
}

bool DFS(int remain)
{
	if(remain == 0) return true;
	else if(vst[remain]) return false;
	else {
		vst[remain] = true; int i;
		for(i = min(ucap, remain); i >= dcap; i--)
			if(bottle[i] && DFS(remain-i)) return true;
		return false;
	}
}