JZOJ 1242 PermRLE

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

排列？k≤16？状压！
显然主体的转移复杂度不能和字符串长度相关，而是用预处理代替。
设这个长度为 m，并设 n=k（不要问为什么，个人爱好）。

设 fS,i,j 表示目前拼成的排列用到的数构成集合 S，这个排列的首项为 i，末项为 j。
设 vi,j 表示所有 mn 段中有多少段第 i 个字符和第 j 个字符不相等。
设 wi,j 表示所有 mn−1 段中有多少段第 i 个字符和下一段的第 j 个字符相等。

显然有转移 fS⋃{k},i,k=minj∈S(fS,i,j+vi,j)(k∉S)。
统计答案时，求 mini,j∈full,i≠j(ffull,i,j−wj,i)(full=n⋃i=1{i})。

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

代码：

#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);
}