[CodeForces - 607B] Zuma

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

链接

\(\text{CodeForces - 607B}\)

题意

  这是一个类似于祖玛的游戏，你有一个长度为\(\text{N}\)的序列\(c\)，序列中一个联通块可以消去（即删除，类似消一消，只能一个联通块一个联通块的消去），一个联通块即是一个连续的子序列，且该子序列是回文的，一个联通块被消去就不存在了，问最少需要消几次。

  数据范围：\(1\le N \le 500,1\le c_i\le N\).

分析

  这是一道区间\(dp\)的题目；这道题的原型是括号序列；

  对于一个序列，对于它的区间长度为\(len\)的阶段，区间长度小于\(len\)的阶段的所有状态，我们已经求出来了，之后对于阶段\(len\)，我们枚举起始点\(i、j\)，对于区间\([i,j]\)，需要枚举划分点\(k\)，如果找到满足\(c[i]==c[k]\)的\(k\)，那么就有\(dp[i][j]=\min\{dp[i][j],dp[i][k]+dp[k+1][j]\}\)，另外我们还需要考虑一种特殊情况，对于区间长度为\(2\)，如果是回文串，我们需要额外判断一下。

  对于初始状态\(dp[i][i]=0\)，其他为\(\infty\).

代码

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
#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 MOD 99991
#define N 200005
#define P 2
 
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, m, a[509], dp[10009][509];
string s;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i], dp[i][i] = 1;
	for (int len = 2; len <= n; len++)
		for (int i = 1; i + len - 1 <= n; i++) {
			int j = i + len - 1;
			dp[i][j] = dp[i + 1][j] + 1;
			for (int k = i + 1; k <= j; k++)
				if (a[i] == a[k])
					dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j] + (i + 1 == k));
			//cout << i << " " << j << " " << dp[i][j] << endl;
		}
	cout << dp[1][n] << endl;
}