解題區/解題區 - UVa

UVa 12283 - Halloween Costumes

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
11
12
13
4 
1 1 
1 
2 2 
1 1 
3 2 
1 2 1 
7 3 
1 2 1 1 3 2 1

Sample Output

1
2
3
4
Case 1: 1
Case 2: 1
Case 3: 2
Case 4: 4

Solution

dp[l][r] 表示參與區間 [l, r] 從 l 開始的最少服裝數。

假設一開始已經穿著 l-th 的服裝，則將可以在參加完後脫掉，或者是到同一個另外一個場所之後考慮是否要脫掉。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int dp[105][105], a[105];
int dfs(int l, int r) {
    if(l > r)	return 0;
    int &ret = dp[l][r];
    if(ret != -1)	return ret;
    ret = min(dfs(l+1, r), dfs(l, r-1))+1;
    for(int i = l+1; i <= r; i++) {
        if(a[l] == a[i])
            ret = min(ret, dfs(l+1, i) + dfs(i+1, r));
    }
    return ret;
}
int main() {
    int cases = 0, testcase, n, m;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        memset(dp, -1, sizeof(dp));
        printf("Case %d: %d\n", ++cases, dfs(0, n-1));
    }
    return 0;
}