解題區/解題區 - UVa

UVa 11523 - Recycling

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Output for Sample Input
  6. 6. Solution

Problem

Recycling involves processing used materials into new products in order to prevent the waste of potentially useful materials.

Recycling materials include things like glass, paper, plastic, metal and textiles. There are some materials that can’t be recycled such as Aerosol Cans. Aerosol cans that are not empty may leak or explode during the sorting and baling processes of recycling.

You are given a list of materials to be recycled. The materials are initially aligned in a line one after another. For every type of recyclable-material there is a corresponding bin. You are required to place each recyclable-material in its corresponding bin.

Example:

paper – glass – paper – aerosol – paper

In the example above, there are two types of recyclable-materials (paper & glass) and one type of non-recyclable-material. If we were to pick each material one by one and throw them in the bins, we would require 4 moves since there are 4 recyclable-materials. However, if we remove consecutive items in one move, provided they are of the same type, we could achieve the desired task in lesser number of moves.

Let’s see how this can be done: If we remove the glass first then the first two papers appear side by side enabling them to be moved together in the next move. Then we just have one paper remaining at the end and that requires a further move. This accumulates to a figure of 3 moves.

Illustration:

1
2
3
4
# Start  : paper – glass – paper – aerosol – paper  
# Move 1 : paper – paper – aerosol – paper [ after removing glass ]   
# Move 2 : aerosol – paper  [ after removing first 2 papers ]   
# Move 3 : aerosol [ after removing the last paper ]

Input

The first line of input is an integer T(T<50) that indicates the number of test cases. Each case starts with an integer N(N<100). The next line contains the names of N materials. The name of each material is a string containing only characters from the set [a..z] and [A..Z] and the length of each is at most 20. A recyclable-material is represented by lowercase letters only and that of non-recyclable-material by uppercase letters only.

Output

For each case, output the case number followed by the minimum number of moves required to clean up all the recyclable-materials meeting the constraints mentioned above.

Sample Input

1
2
3
4
5
6
7
3
5
paper glass paper AEROSOL paper
4
icpc icpc icpc icpc
3
NO RECYCLABLE MATERIALS

Output for Sample Input

1
2
3
Case 1: 3
Case 2: 1
Case 3: 0

Solution

題目描述：

現在把垃圾放置在一維空間，垃圾分成可回收和不可回收兩種，我們可以一次將連續個回收物拾起清除 (整個區間內的回收種類都要相同。) 並且放置回收桶。

用小寫表示可回收的種類分布，大寫為不可回收。求操作次數最少為何。

題目解法：

這一題比 UVa 10559 - Blocks 還要稍微簡單一點，可以在 O(n^3) 以內完成。UVa 10559 - Blocks 的計分方式多了一次清除的個數平方，最大化分數。

在這裡我們只需要將狀態改為，考慮區間 [l, r] 最左側 A[l] 項目是否要清除，否則將要等待 [l+1, i] 之間的項目清除之後，與 [i+1, ...] 一起清除。

  • 直接移除最左側
  • 等待中間一段的移除，隨後跟著 [i+1, ...] 最左側的一起清除。

因此轉移方程

$dp[l, r] = min(min(dp[l+1, r] + 1), min(dp[l+1, i] + dp[i+1, r]))$

記住中間轉移要保證一定取得連續相同且皆可回收，為了方便計算，連續相同的壓縮起來，直接考慮是否可回收即可。

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
// http://mypaper.pchome.com.tw/zerojudge/post/1326837348
#include <stdio.h>
#include <map>
#include <iostream>
#include <algorithm>
#include <ctype.h>
using namespace std;
int A[105], B[105];
int dp[105][105]; //[l][r][___{l, r}]
char used[105][105] = {}, usedcases = 0;
int dfs(int l, int r) {
    if(l > r)    return 0;
    if(used[l][r] == usedcases)
        return dp[l][r];
    int &ret = dp[l][r];
    used[l][r] = usedcases;
    if(A[l] == -1) {
    	ret = dfs(l + 1, r);
    	return ret;
    }
    ret = dfs(l+1, r) + 1;
    for(int i = l+1; i <= r && A[i] != -1; i++) {
        if(A[i] == A[l]) {
            ret = min(ret, dfs(l+1, i-1) + dfs(i, r));
        }
    }
    return ret;
}
int main() {
    int testcase, n, m;
    int cases = 0, i;
    char material[105][32];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        
        map<string, int> R;
        for(int i = 0; i < n; i++) {
        	scanf("%s", material[i]);
        	if(islower(material[i][0]))
        		R[material[i]] = 0;
        }
        
        int size = 0;
        for(map<string, int>::iterator it = R.begin(); it != R.end(); it++)
        	it->second = size++;
        for(int i = 0; i < n; i++)	 {
        	if(isupper(material[i][0]))
        		A[i] = -1;
        	else
        		A[i] = R[material[i]];
        }
        
        for(i = 1, B[0] = 1, m = 0; i < n; i++) {
            if(A[m] == A[i])
                B[m]++;
            else {
                A[++m] = A[i], B[m] = 1;
            }
        }
        usedcases++;
        printf("Case %d: %d\n", ++cases, dfs(0, m));
    }
    return 0;
}