[CF - 1132F] Clear the String

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

链接

\(\text{CF - 1132F}\)

题意

  给你一个长度为\(\text{N}\)的由小写字母组成的字符串\(s\)，你需要对它进行删除操作，你每次可以删除一个连续的、只含一种字母的子串，现在问你最少需要多少次可以把它含有的字符全部删除掉。   数据范围：\(1\leq \text{N} \leq 500\).

分析

  这是一道区间\(dp\)的题目；

  首先\(dp[i][j]\)表示把\([i,\ j]\)的字符全部删除需要进行的最少操作次数，正常情况下，我们需要枚举区间长度、起点及终点；对于一个区间\([l,r]\),，如果\(s[l]==s[r]\)，那么\(dp[l][r]\)，一定等于\(dp[l+1][r]\)、\(dp[l][r-1]\)二者中较小者，如果\(s[l]!=s[r]\)，我们就需要枚举划分点作为转移决策，有转移方程：\(dp[i][j]=\displaystyle \min_{i\leq k < j}\{dp[i][k]+dp[k+1][j]\}\)。   对于\(dp[i][j]\)的初值应该初始化为\(i-j+1\)。

代码

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 <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, m, dp[504][503];
int cnt;
string s;
int main() {
	cin >> n;
	cin >> s;
	memset(dp, INF, sizeof(dp));
	for (int i = 1; i <= n; 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;
			if (s[i - 1] == s[j - 1])
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
			else {
				for (int k = i; k < j; k++)
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
			}
		}
	}
	cout << dp[1][n] << endl;
}