第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明） Cities (区间DP)

157 阅读 0 评论 104 点赞

我是靠谱客的博主威武店员，这篇文章主要介绍第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明） Cities (区间DP)，现在分享给大家，希望可以做个参考。

Cities (区间DP)

题目链接

大致题意:

一个长度为 n 的数组，一次操作可以选择一段连续值相同的区间，使其变成其他值，问最少需要多少次操作，才能使得数组的值全相等

数组中每个数最多出现15次

解题思路:

首先将数组去重,使得相邻元素不同,定义last[i]表示为上一次a[i]出现的位置(这是关键,因为我们要尽量减少操作次数,所以我们尽可能选择左右端点相同的进行操作)

有f[l+1][r]+1和f[l][r-1]+1两种转移,我们定左端点,从右往左进行dp,即f[l][r] = f[l][r - 1] + 1

AC代码:

复制代码

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
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 6010;
int n;
int a[N], b[N];
int f[N][N];
int last[N], pos[N];
int main(void)
{
	int t; scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) {
			pos[i] = 0;
			scanf("%d", &a[i]);
		}

		int cnt = 0;
		for (int i = 1; i <= n; ++i)
			if (a[i] != a[i - 1])b[++cnt] = a[i];
		for (int i = 1; i <= cnt; ++i) {
			last[i] = pos[b[i]];
			pos[b[i]] = i;
		}
		n = cnt;
		memset(f, INF, sizeof f);
		for (int i = 1; i <= n; ++i)
			f[i][i] = 0, f[i + 1][i] = 0;
		
		for (int len = 1; len < n; ++len)
			for (int l = 1; l <= n - len; ++l) {
				int r = l + len;
				f[l][r] = f[l][r - 1] + 1;
				for (int k = last[r]; k >= l; k = last[k]) {
					f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
				}
			}
		printf("%dn", f[1][n]);
	}
	return 0;
}