hihocoder-1400-compostion

发表于   |   分类于   |  

题目大意

　　此题是2017微软秋季校园招聘在线编程笔试的第二题

　　http://hihocoder.com/problemset/problem/1400

　　一个长度为N的字符串，已知有M个字符对不能相邻，让你求为满足此性质，原字符串的最少删除字符个数。

题目分析

  • 第一种思路，原题实际上是求满足某种特殊条件的最长子序列，这种特殊条件是满足给定的M对字符不能相邻，所以此题很像最长升序子序列，又注意到，本题字符数一共就26个。可以采用动态规划的思路，我们要维护一个长度为26的数组，也就对应26个英文字母，对应存的值是以该下标字母为结尾所能构成满足条件的最长子序列。，比如f['a' - 'a']存的就是以字母a为结尾的子序列的最大长度。原字符串为str，假设扫描到某个位置i，那么从第0个位置到第i个位置的所能构成的最长子序列其实是遍历f[j]，j跟i所构成的长度为2的字符串满足条件的最大值。实质上，我们要从前到后扫描整个字符串，一直更新f数组的值。最后求的结果就是N-max{f[i]}
  • 第二种思路，记忆化搜索的思路，从前向后搜索字符串，每个位置都可以选择要或者不要，但是由于一些字符之间不能相邻，所以扫描到特定字符时，必须不要，因为跟已纪录的字符串最后一个冲突，如果不冲突还是有两种选择，要或者不要。但是有个问题，初始时，字符串的第一个字符到底是要还是不要，可以简化一下，认为在原字符串前加入一个字符，该字符的ascii值为'a' - 1 这样这个字符不可能跟任何字符产生冲突，换句话说，新构造出的字符串所求的结果跟原字符串相同，之后代码就是标准的dfs的思路。不过这样肯定会超时，因为存在重复计算，需要记录一些东西。引入一个二维数组f，f的第一维存的是已搜索保存的结果最后一位字符，第二维是将要搜索的位置index，比如f[c][5]的含义是搜索路径最后一个是字符c，并且下一个搜索的是第五个字符串时，从第五个字符串到最后一个字符串能够是搜索路径增加的长度。

代码

第一种思路
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
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX_SIZE 100005
using namespace std;
bool m[202][202];
int f[27];
int search(const int len, char str[]) {
    int maxf = 0x80000000;
	for(int i = 0; i < len; i++) {
        int v = f[str[i] - 'a'];
		for(int j = 0; j <= 26; j++) {
			if(!m[j][str[i] - 'a']) {
				v = max(v, f[j] + 1);
			}
		}
		f[str[i] - 'a'] = max(v, 1);
		maxf = max(f[str[i] - 'a'], maxf);
	}
	return maxf;
}
int main() {
	int N;
	scanf("%d", &N);
	char str[MAX_SIZE];
	scanf("%s", str);
	int M;
	scanf("%d", &M);
	memset(m, 0, sizeof(m));
	memset(f, 0, sizeof(f));
	for(int i = 0; i < M; i++) {
		char tmp[3];
		scanf("%s", tmp);;
		m[tmp[0] - 'a'][tmp[1] - 'a'] = true;
		m[tmp[1] - 'a'][tmp[0] - 'a'] = true;
	}
	int ans = search(N, str);
	printf("%d\n", N - ans);
	return 0;
 }

　　复杂度：O(max{N,M})

第二种思路
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
57
58
59
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX_SIZE 100005
using namespace std;
char path[MAX_SIZE];
bool m[202][202];
int f[27][MAX_SIZE];
int search(int idx,const int len, int last, char str[]) {
	if(idx > len - 1) {
		return 0;
	}
	if(f[path[last] - 'a' + 1][idx] >= 0) {
        return f[path[last] - 'a' + 1][idx];
	}
    bool it1 = m[path[last] - 'a' + 1][str[idx] - 'a' + 1];
    bool it2 = m[str[idx] - 'a' + 1][path[last] - 'a' + 1];
	if(it1 || it2) {
		//delete idx
		f[path[last] - 'a' + 1][idx] = search(idx + 1, len, last, str);
        return f[path[last] - 'a' + 1][idx];
	} else {
		//delete idx
        int v1 = search(idx + 1, len, last, str);
        //not delete idx
        path[last + 1] = str[idx];
		int v2 = 1 + search(idx + 1, len, last + 1, str);
		int v =  ((v1>v2) ?v1 :v2);
		f[path[last] - 'a' + 1][idx] = v;
		return v;
	}
}
int main() {
	int N;
	scanf("%d", &N);
	char str[MAX_SIZE];
	scanf("%s", &(str[1]));
	str[0] = 'a' - 1;
	int M;
	scanf("%d", &M);
	memset(m, 0, sizeof(m));
	memset(f, -1, sizeof(f));
	for(int i = 0; i < M; i++) {
		char tmp[3];
		scanf("%s", tmp);;
		m[tmp[0] - 'a' + 1][tmp[1] - 'a' + 1] = true;
	}
	path[0] = str[0];
	int ans  = search(1, N + 1, 0, str);
	printf("%d\n", N - ans);
	return 0;
 }

　　复杂度：O(MAX_SIZE*27)