0%

深信服校园招聘c/c++软件开发G卷-T1序列组装

题目链接

题面截图

题解

要求复杂度在$O(n^{2}(2^{n}+l))$内,很显然这样的复杂度应该是用状压dp。

令$dp[i][j]$表示已经放了$i$的状态下,最后放入的是第$j$个字符串的最小答案。(这里的$j$下标从$0$开始)

那么就有这样的状态转移:

首先如果状态$i$中只有一个字符串,那么$dp[1 << j][j]=len[j]$。($len[j]$表示第$j$个字符串的长度)

那么对于状态$i$中不止有一个字符串的,且有$j \in i$的有:
$$dp[i][j]=\min\limits_{k=0}^{n-1}(dp[i \oplus (1 << j)][k] + len[j] - tmp[k][j])$$

这里表示的意思是当前是要放第$j$个字符串,然后上一个字符串是第$k$个字符串,然后转移。其中$tmp[k][j]$的意思是前面先放第字符串$k$后面放字符串$j$所能缩短的最多字符大小。

状压dp部分的复杂度就已经到达$O(n^{2}(2^{n}+l))$了,如果再在里面再求tmp数组的话复杂度会很高。

很显然需要预处理tmp数组。如何去预处理呢?

最暴力的方式就是直接枚举前缀后缀进行比较,但是这样的话复杂度会到达$O(n^2\cdot l^2)$,不能达到预期。

可以想到字符串的一些方法来优化$O(l^2)$的部分把它优化成$O(l)$,例如后缀数组、后缀自动机、z_function之类的算法。

我是用的是z_function,写起来比较短,而且很好用。

z_function是输入一个长度为$n$的字符串$s$然后$O(n)$处理出第$i$个位置的后缀与$s$的前缀的最长公共前缀长度。

于是把用一个字符串str2 + “*”(一个未出现过的字符) + str1扔进z_function得到z数组,那么对于$i>l+1$的部分中,如果$z[i]=2\cdot l-i$就表示这个$z[i]$可以作为两个字符串重叠的部分。枚举两个字符串后做到了$O(l)$处理。即总的预处理字符串的复杂度是$O(n^2\cdot l)$。

那么预处理加上状压dp的复杂度是$O(n^2\cdot l+n^2\cdot 2^{n})$达到了预期。

代码

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
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
string str[11];
int dp[1 << 11][11];
int tmp[11][11];
vector<int> z_function(string s) {
int n = (int)s.length();
vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i <= r) z[i] = min(r - i + 1, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
return z;
}
int main() {
int T; cin >> T;
while(T--) {
int n, l; cin >> n >> l;
for(int i = 0; i < n; i++) {
cin >> str[i];
}
// 预处理tmp数组
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
tmp[i][j] = 0;
string nw = str[j] + "$" + str[i];
vector<int> z = z_function(nw);
const int sz = nw.size();
for(int k = int(str[j].size()) + 1; k < sz; k++) {
if(sz - k == z[k]) {
tmp[i][j] = z[k];
break;
}
}
}
}
// 置为最大值
for(int i = 0; i < (1 << n); i++) {
for(int j = 0; j < n; j++) {
dp[i][j] = 0x3f3f3f3f;
}
}
// dp初始值
for(int i = 0; i < n; i++) {
dp[1 << i][i] = str[i].size();
}
// 状压dp
for(int i = 0; i < (1 << n); i++) {
const int cur = __builtin_popcount(i);
if(cur == 1) continue;
for(int j = 0; j < n; j++) {
if((i >> j) & 1) {
for(int k = 0; k < n; k++) {
dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + int(str[j].size()) - tmp[k][j]);
}
}
}
}
int mn = INT_MAX;
for(int i = 0; i < n; i++) {
mn = min(mn, dp[(1 << n) - 1][i]);
}
cout << mn << '\n';
}
}

回到开头