动态规划

第一章 状压 Dp

状压 $Dp$ 是一种很有技巧性且较为抽象的 $Dp$ 问题，也是中高级比赛的常考题型。

下面，笔者会尽力帮助大家理解并深入这个算法，如果这篇对您能有所帮助，希望您可以点一个赞或者一个关注。

状压的实现

在部分 $NPC$ 问题中，状态的转移和表示往往需要花费大量的时间。

但其中往往会有一些规律，这些规律如果是用 $DFS$ 加速的话，却又过于抽象且常数较大。

状压 $DP$, 便是在这一类题上富有优势。

状压 $DP$, 虽称为 $DP$, 本质上却更偏向记搜，对于其无效状态的排除就是其中最困难的一点

状压 Dp 实现组合型枚举

const int N = 26, M = 1 << 21;

int n, m, a, tot;
vector<short> ans[M];
bitset<N> Map;

void work()
{
    for (int i = 0; i <= n; i ++ )
        if (Map[i]) ans[tot].push_back(i + 1);
}

int main()
{
    scanf("%d %d", &n, &m);

    for (int a = 0; a < (1 << n); a ++, Map.reset())    // reset 的意思是清除
    {
        Map |= a;
        if (Map.count() != m) continue;
        tot ++;
        work();
    }
}

没错，正如上面代码所述，状压 $Dp$ 就是在枚举的所有状态中寻找符合条件的状态。