解題區►解題區 - UVa

UVa 10280 - Old Wine Into New Bottles

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Solution

Problem

給予 n 種酒瓶，每一種酒瓶有其裝酒的容積上下限 [min, max] 毫升，請問將 m 公升的酒裝入酒瓶，最後剩餘的最少量為多少。

每一種酒瓶可以無限使用。

Input

1
2
3
4
5
6
7
8
9
2
10 2
4450 4500
725 750
10000 2
4450 4500
725 750

Output

1
2
3
250
0

Solution

這一題需要剪枝，無法單純地運行背包 dp，單純的背包 dp 很容易造成 TLE。

發現到只考慮使用一種酒瓶，那麼當酒量大於某個定值後，保證都能裝完。假設使用單一酒瓶的數量為 k 個以上時，能裝出所有量，則能覆蓋的區間為

1
[min, max], ..., [k*min, k*max], [(k+1)*min, (k+1)*max]

當第 k+1 個區間的左端點小於第 k 個區間的右端點時，可以得到接下來的所有區間都會發生重疊。推導得到 (k+1)*min >= k*max 最後條件 k >= min / (max - min)。

滿足保證能裝出，直接輸出答案 0，否則做背包 dp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h> 
#include <algorithm>
#include <string.h>
using namespace std;
#define MAXL (1000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXL];
/*
	k bottles
	[min, max], ..., [k*min, k*max], [(k+1)*min, (k+1)*max]
	
	always have solution for [k*min, k*max], [(k+1)*min, (k+1)*max] 
	sat. (k+1)*min >= k*max 
			k >= min / (max - min)
	all interval cover each other after k-bottles.
*/
const int MAXN = 128;
int mx[MAXN], mn[MAXN];
int main() {
	int testcase, L, N;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &L, &N);
		L *= 1000;
		
		int lower_full = 0x3f3f3f3f; 
		for (int i = 0; i < N; i++) {
			scanf("%d %d", &mn[i], &mx[i]);
			lower_full = min(lower_full, mn[i] * mn[i] / (mx[i] - mn[i]));
		}
		
		if (L >= lower_full) {
			puts("0");
			if (testcase)
				puts("");
			continue;
		}
		
		// limit L <= 4500 * 4500 / (4500 * 0.01)
		int A[4505] = {}, ret = 0;
		
		for (int i = 0; i < N; i++)
			for (int j = mn[i]; j <= mx[i]; j++)
				A[j] = 1;
			
		memset(mark, 0, sizeof(mark)); 
		SET(0);
		for (int i = 1; i <= 4500; i++) {
			if (A[i] == 0)
				continue;
			for (int j = i, k = 0; j <= L; j++, k++) {
				if (GET(k))
					SET(j), ret = max(ret, j);
			}
		}
		
		printf("%d\n", L - ret);
		if (testcase)
			puts("");
	}
	return 0;
}
/*
2
10 2
4450 4500
725 750
10000 2
4450 4500
725 750
*/