『Exclusive Access 2 dilworth定理 状压dp』

我们其实变相证明了著名的\(dilworth\)定理：偏序集的最长链等于其最小反链划分。

然后直接枚举点集，状压预处理出其划分方式是否合法，然后枚举子集\(dp\)即可。

\(Code:\)

#include <bits/stdc++.h>
using namespace std;
const int N = 16;
int n,m,a[N][N],p[1<<N],f[1<<N];
vector < pair<char,char> > Link;
map <char,int> Hash;
int main(void)
{
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
    {
        char c1,c2;
        cin >> c1 >> c2;
        Link.emplace_back(c1,c2);
        Hash[c1] = Hash[c2] = true;
    }
    map <char,int> :: iterator it;
    for (it=Hash.begin();it!=Hash.end();it++)
        it -> second = ++n;
    for ( auto e : Link )
        a[Hash[e.first]][Hash[e.second]] = a[Hash[e.second]][Hash[e.first]] = 1;
    memset( f , 0x3f , sizeof f );
    for (int S=1;S<1<<n;S++)
        for (int i=1;i<=n;i++)
            if ( S >> (i-1) & 1 )
                for (int j=i+1;j<=n;j++)
                    if ( S >> (j-1) & 1 )
                        p[S] |= a[i][j];
    f[0] = 0;
    for (int S=1;S<1<<n;S++)
        for (int T=S;T;T=S&(T-1))
            if ( p[T] == 0 )
                f[S] = min( f[S] , f[S^T] + 1 );
    printf("%d\n",f[(1<<n)-1]-2);
    return 0;
}