JZOJ 1242.PermRLE

据说是 Google Code Jam 2008 的题,好像还可以转化为求 Hamilton 路径?
我太弱了太弱了,不懂。

排列?k16k \le 16?状压!
显然主体的转移复杂度不能和字符串长度相关,而是用预处理代替。
设这个长度为 mm,并设 n=kn = k(不要问为什么,个人爱好)。

fS,i,jf_{S,i,j} 表示目前拼成的排列用到的数构成集合 SS,这个排列的首项为 ii,末项为 jj
vi,jv_{i,j} 表示所有 mn\dfrac m n 段中有多少段第 ii 个字符和第 jj 个字符相等。
wi,jw_{i,j} 表示所有 mn1\dfrac m n - 1 段中有多少段第 ii 个字符和下一段的第 jj 个字符相等。

显然有转移
统计答案时,求 mini,jfull,ij(ffull,i,jwj,i)(full=i=1n{i})\min\limits_{i,j \in full,i \ne j}(f_{full,i,j} - w_{j,i})\,(full = \bigcup\limits_{i = 1}^n \{i\})

注意这样子空间复杂度是 O(2nn2)O(2^nn^2) 的,而题目卡了空间 TAT……
注意到 ii 这一维在转移的时候是不变的,所以可以压掉这一维,并把 ii 放在最外层枚举。
总复杂度 O(mn+2nn3)O(mn + 2^nn^3)

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 16;
const int M = 5e4;
int n,m,full;
char s[M + 5];
int w[N + 5][N + 5],v[N + 5][N + 5];
int f[(1 << 16) + 5][N + 5];
int ans = 0x3f3f3f3f;
int main()
{
scanf("%d%s",&n,s + 1),m = strlen(s + 1),full = (1 << n) - 1;
for(register int i = 1;i <= m;i += n)
for(register int j = 1;j <= n;++j)
for(register int k = 1;k <= n;++k)
w[j][k] += (bool)(s[i + j - 1] ^ s[i + k - 1]);
for(register int i = 1;i + n <= m;i += n)
for(register int j = 1;j <= n;++j)
for(register int k = 1;k <= n;++k)
v[j][k] += (bool)(s[i + j - 1] == s[i + n + k - 1]);
for(register int j = 1;j <= n;++j)
{
memset(f,0x3f,sizeof f);
f[1 << j - 1][j] = m / n;
for(register int i = 0;i <= full;++i)
if(i & (1 << j - 1))
for(register int k = 1;k <= n;++k)
if(i & (1 << k - 1))
for(register int l = 1;l <= n;++l)
if(!(i & (1 << l - 1)))
f[i | (1 << l - 1)][l] = min(f[i | (1 << l - 1)][l],f[i][k] + w[k][l]);
for(register int i = 1;i <= n;++i)
ans = min(ans,f[full][i] - v[i][j]);
}
printf("%d\n",ans);
}