解題區/解題區 - UVa

UVa 12654 - Patches

contents

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

Problem

輪胎上有數個洞需要補丁，只有兩種補丁，每個補丁長度不同，求用總長度最少的補丁覆蓋所有的洞。

Sample Input

1
2
3
4
5
6
7
8
9
10
5 20 2 3
2 5 8 11 15
4 20 12 9
1 2 3 13
2 10 3 2
0 9
2 10 3 2
0 2
2 10 3 2
0 3

Sample Output

1
2
3
4
5
8
12
2
2
3

Solution

這一題最麻煩就是處理環的部分，事實上我們可以窮舉補丁的起始位置，然後針對這一個位置進行 O(n) 計算 DP 最小值。

因此最後能在 O(n^2) 完成，為了簡化計算，直接對陣列的 rotate shift left 操作。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int F[1024];
int main() {
    int N, C, T[2];
    while(scanf("%d %d %d %d", &N, &C, &T[0], &T[1]) == 4) {
        for(int i = 0; i < N; i++)
            scanf("%d", &F[i]);
        sort(F, F+N);
        int ret = 0x3f3f3f3f;
        for(int i = 0; i < N; i++) {
            int dp[1024] = {};
            for(int j = 0; j <= N; j++)
                dp[j] = 0x3f3f3f3f;
            dp[0] = 0;
            int cover1 = 0, cover2 = 0;
            for(int j = 0; j < N; j++) {
                while(cover1 + 1 < N && F[cover1 + 1] - F[j] <= T[0])
                    cover1++;
                while(cover2 + 1 < N && F[cover2 + 1] - F[j] <= T[1])
                    cover2++;
                dp[cover1+1] = min(dp[cover1+1], dp[j] + T[0]);
                dp[cover2+1] = min(dp[cover2+1], dp[j] + T[1]);
            }
            ret = min(ret, dp[N]);
            swap(F[0], F[N]);
            F[N] += C;
            for(int j = 0; j < N; j++)
                F[j] = F[j+1];
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
5 20 2 3
2 5 8 11 15
4 20 12 9
1 2 3 13
2 10 3 2
0 9
2 10 3 2
0 2
2 10 3 2
0 3
*/