CF - 1117 F Crisp String

题目传送门

题解：

枚举非法对。

　　如果 ‘a' 和 ’b' 不能相邻的话，那么删除 'a' 'b'之间的字符就是非法操作了。假设题目给定的字符串为 "acdbe"，所以删除cd是非法操作，因为cd是非法了，所以cde也是非法操作，

　　　　也就是说找到所有的非法操作之后往外推，比他多删的状态就一样是非法的了，当然对于上述的“acdbe"来说，不能确定 ”acd"是非法操作，因为在枚举非法对的时候，该非法对的字符并不能被删除。

然后把所有非法对的非法状态都存下来。然后从没删除的状态往外搜，就好了。

代码：

/*

code by: zstu wxk

time: 2019/03/06

Problem Link: http://codeforces.com/contest/1117/problem/F

Solve:

*/

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 1e5 + ;

char s[N];

int a[][], cnt[];

int tmp[<<], gg[<<];

int n, m, k;

void solve(int u, int v){

    memset(tmp, , sizeof(tmp));

    for(int i = , j; i <= n;){

        while(i <= n && s[i]-'a' != u) ++i;

        int t = ;

        j = i+;

        while(j <= n && s[j] -'a' != u && s[j]-'a' !=  v) {

            t |=  << s[j]-'a';

            ++j;

        }

        if(j > n) break;

        if(s[j] - 'a' == v){

            i = j+;

            tmp[t] = ;

        }

        if(s[j] - 'a' == u)

            i = j;

    }

    for(int i = ; i <= k; ++i){

        if(tmp[i]){

            gg[i] = ;

            for(int j = ; j < m; ++j){

                if(j == u || j == v) continue;

                tmp[i|(<<j)] = ;

            }

        }

    }

    return ;

}

int vis[<<];

int ans;

void DFS(int x, int len){

    if(vis[x]) return ;

    vis[x] = ;

    ans = min(ans, len);

    for(int i = ; i < m; ++i){

        if(gg[x | (<<i)]) continue;

        DFS(x|<<i, len-cnt[i]);

    }

    return ;

}

void Ac(){

    memset(gg, , sizeof(gg));

    memset(cnt, , sizeof cnt);

    scanf("%s", s+);

    for(int i = ; i < m; ++i)

        for(int j = ; j < m; ++j)

            scanf("%d", &a[i][j]);

    k = (<<m) - ;

    for(int i = ; i < m; ++i)

        for(int j = ; j < m; ++j)

            if(a[i][j] == )

                solve(i,j);

    for(int i = ; i <= n; ++i){

        cnt[s[i]-'a']++;

    }

    ans = n;

    DFS(, n);

    printf("%d\n", ans);

    return ;

}

int main(){

    while(~scanf("%d%d", &n, &m)){

        Ac();

    }

    return ;

}