[LightOJ - 1422] Halloween Costumes

发表于 | 更新于 | 分类于 ， ，
本文字数： 9.8k

链接

\(\text{LightOJ - 1422}\)

题意

  这里有\(n\)次宴会，每个宴会有一个特定的编号，每个宴会需要一件特定衣服，\(n\)次宴会有顺序，衣服可以套着穿，一件衣服脱下后不能在穿，问最少需要买多少件衣服，如宴会为1、2、1、2，开始买衣服1，然后买衣服2，第三个宴会为1，此时身上是有宴会1的衣服的，不过外面还有一件宴会2的衣服，所以需要脱掉衣服2，第四个宴会为2，此时需要再买一件；

分析

  这是一道区间\(dp\)的题目；从左往右考虑，对于一件衣服，可以选择脱与不脱，贪心的考虑肯定是不脱较好，这题需要从右往左进行枚举；

  对于区间\(dp\)来说，是枚举区间长度，及起始点的，然后找划分点作为决策；对于区间\([l,r]\)我们需要求它的最少需要购买的衣服，我们此时肯定需要去看\([l+1,r]\)的状态（如看区间\([l+1,r]\)有没有出现\(l\)这件衣服，如果有，我们可能会思考是不是不需要再多购买一件了，类似这样的想法），所以我们就需要在\([l+1,r]\)区间内寻找划分点\(k(a[l]==a[k])\)作为状态转移决策，就有了动态转移方程\(dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j])(a[i]==a[k])\).

代码

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
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define P 2
#define MOD 99991

typedef long long ll;

namespace fastIO {
	//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
	//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
	inline int read() {
		char c = getchar(); int x = 0, f = 1;
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
		return x * f;
	}
}

using namespace fastIO;
using namespace std;

int t, n, dp[130][130], a[130], cnt;

int main() {
	cin >> t;
	while (t--) {
		cin >> n;
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		for (int i = n; i > 0; i--)
			for (int j = i; j <= n; j++) {
				dp[i][j] = dp[i + 1][j] + 1;
				//cout << i << " " << j << " " << dp[i][j] << " ";
				for (int k = i + 1; k <= j; k++)
					if (a[k] == a[i])
						dp[i][j] = min(dp[i][j], dp[i + 1][k] + dp[k + 1][j]);
				//cout << dp[i][j] << endl;
			}
		printf("Case %d: %d\n", ++cnt, dp[1][n]);
	}
}