据说是 Google Code Jam 2008 的题，好像还可以转化为求 Hamilton 路径？
我太弱了太弱了，不懂。
排列？\(k \le 16\)？状压！
显然主体的转移复杂度不能和字符串长度相关，而是用预处理代替。
设这个长度为 \(m\)，并设 \(n = k\)（不要问为什么，个人爱好）。
设 \(f_{S,i,j}\) 表示目前拼成的排列用到的数构成集合 \(S\)，这个排列的首项为 \(i\)，末项为 \(j\)。
设 \(v_{i,j}\) 表示所有 \(\dfrac m n\) 段中有多少段第 \(i\) 个字符和第 \(j\) 个字符不相等。
设 \(w_{i,j}\) 表示所有 \(\dfrac m n - 1\) 段中有多少段第 \(i\) 个字符和下一段的第 \(j\) 个字符相等。
显然有转移 \(f_{S\bigcup\{k\},i,k} = \min\limits_{j\in S}(f_{S,i,j} + v_{i,j})\,(k\not\in S)\)。
统计答案时，求 \(\min\limits_{i,j \in full,i \ne j}(f_{full,i,j} - w_{j,i})\,(full = \bigcup\limits_{i = 1}^n \{i\})\)。
注意这样子空间复杂度是 \(O(2^nn^2)\) 的，而题目卡了空间 TAT……
注意到 \(i\) 这一维在转移的时候是不变的，所以可以压掉这一维，并把 \(i\) 放在最外层枚举。
总复杂度 \(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
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);
}