Crisp String（状压dp）

题意：

给定长度为的字符串序列，由前个小写字母构成的串，一个的矩阵，若矩阵中则说明，字符与字符可以相邻，反之则不能。问：在保持相邻字符的约束下，不断删除某种字符的所有出现，串最短能变得有多短？

题解：

本题字符集规模不大，但有两个大参数：字符串长度和字符集大小。若算法需要次计算，必定超时。注意到每种字符子集是否可删如果都求出了，结果自然得到，但枚举字符集可删需要次计算，即使利用子集间的联系也很难将单个子集的判断计算量降阶。
一个好办法是枚举每对不可相邻的字符，然后在字符串中扫描一遍发现不能删的子集，因为的位置到下一个的位置之间的出现字符肯定是不能删的。如图：

而除了这个子集剩下的集合对于这对不可相邻的字符都是可以的，那么就先将剩余的集合都先标记为1，即，表示x字符序列是可删的，但是要能将也删掉，所以最终再遍历一遍所有的字符集，将包含这对不可相邻的字符的字符序列的记录下来，即,就表示这个字符序列是可删了。
统计完所有的可删序列后，从全集出发，枚举不可删序列的最小值，如果枚举到的当前序列可删就结束，因为可删的序列子集同样可删。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m, mx, ans = INF;
char s[N];
int a[N], tmp[1 << 17], f[1 << 17];
int cst[1 << 17], dp[1 << 17];
int g[17][17];

void dfs(int x)
{
    if (tmp[x])
        return;
    tmp[x] = 1;
    for (int y = x; y; y ^= y & -y)
        dfs(x ^ y & -y);
}
void dfs1(int x)
{
    if (f[x] || tmp[x])
        return;
    tmp[x] = 1;
    ans = min(ans, cst[x]);
    for (int y = x; y; y ^= y & -y)
        dfs1(x ^ y & -y);
}

int main()
{
    scanf("%d%d%s", &n, &m, s + 1);
    mx = (1 << m) - 1;
    for (int i = 1; i <= n; i++)
        cst[1 << (a[i] = s[i] - 'a')]++;
    for (int i = 1; i <= mx; i++)
        cst[i] = cst[i ^ i & -i] + cst[i & -i];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &g[i][j]);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            if (!g[i][j])
            {
                int now = 0, pre = -1;
                for (int k = 1; k <= n; k++)
                {
                    if (a[k] == i || a[k] == j)
                    {
                        if (a[k] == i && pre == j || a[k] == j && pre == i)
                            dfs(mx ^ now);
                        now = 0, pre = a[k];
                    }
                    else
                        now |= 1 << a[k];
                }
                int t = 1 << i | 1 << j;
                for (int k = 0; k <= mx; k++)
                {
                    if ((k & t) == t)
                        f[k] |= tmp[k];
                    tmp[k] = 0;
                }
            }
    dfs1(mx);
    printf("%d\n", ans);
}