解題區/解題區 - 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
*/