P7859 2 的 n 次方做法

· · 题解

前言：本题 2^n 做法相当巧妙，精读此题解你将会提升很多对 DP 的理解，题解区没有一个是 2^n 做法

https://www.luogu.com.cn/problem/P7859

最傻的一种做法：二进制枚举，枚举披萨配料的放置状态再检查冲突的两个位上是否都是 1

时间复杂度为 O(n^2m)

#include <iostream>
using namespace std;
const int N = 405;
typedef pair<int, int> PII;
PII limit[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) 
        cin >> limit[i].first >> limit[i].second;
    int res = 0;
    for (int i = 0; i < 1 << n; i++)
    {
        bool flag = true;
        //检查是否满足所有的限制
        for (int j = 1; j <= m; j++)
        {
            int x = limit[j].first - 1, y = limit[j].second - 1;
            if ((x != y) && (i >> x & 1) && (i >> y & 1)) 
            {
                flag = false;
                break;
            }
        }
        if (flag) res++;
    }
    cout << res;
    return 0;
}

上述想法非常的傻，产生了大量无效的操作，例如 1 和 2 存在冲突，但是我们不停枚举放 1,2，1,2,3，1,2,3,4 这样就是无效的

刷表法：一般的 DP 都使用填表法（即考虑一个状态可以由哪些状态转移过来），而刷表法是考虑一个状态可以转移到哪些状态去，在某些问题中更加符合人的思维

其实对于这种能否构成的问题，最好的办法就是刷表法（考虑计算机问题时要考虑增量，一步到另一步之间的变化，也就是动态规划中的 最优子结构），对于一个已知的合法状态 i，考虑枚举加入第 j 种配料（为了省空间将第一种变成第零种，整体减去 1），即将 i 的二进制表示下的第 j 位变为 1，二进制 i 就是 DP 中的一个 阶段，而一种配料放或不放就是 DP 中的 决策，将与 j 位置冲突的位置变成二进制数，再与上 i 看是否等于 0（若两个都为 1 结果为 1，表示 i 中出现了与 j 冲突的配料），复杂度成功降至 O(2^nn)

#include <iostream>
using namespace std;
const int N = 25;
int limit[N]; //是否有冲突
bool dp[1 << 20];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) 
    {
        int x, y;
        cin >> x >> y;
        x--, y--;
        limit[x] |= 1 << y;
        limit[y] |= 1 << x;
    }
    dp[0] = 1;
    for (int i = 0; i < 1 << n; i++)
    {
        if (dp[i]) //若状态合法进行刷表
        {
            for (int j = 0; j < n; j++) //枚举哪一位放 1 
                if (!(i >> j & 1) && !(i & limit[j])) 
                    dp[i | 1 << j] = 1;
        }
    }
    int res = 0;
    for (int i = 0; i < 1 << n; i++) res += (dp[i] == 1);
    cout << res;
}

我们可以借鉴刷表法的思路换成填表法，枚举最后一次放的是哪一位，另外考虑一个问题，假如 \{1,2,3,5\} 这个集合是合法的，那么 \{1,2,3\},\{1,2,5\},\{2,3,5\}\dots 这些集合都是合法的，这些集合转化到 \{1,2,3,5\} 分别枚举的是 5,3,1，所以说其实只需要枚举 1 个位置就行了，其余的都是没用的，我们规定只枚举最小的那一位，此时时间复杂度降至 O(2^n)

#include <iostream>
using namespace std;
const int N = 25, M = 1 << 20;
int dp[M], mark[N];
int lowbit(int x)
{
    return x & (-x);
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        mark[a] |= 1 << b;
        mark[b] |= 1 << a;
    }
    int ans = 0;
    dp[0] = 1;
    for (int i = 1; i < 1 << n; i++)
    {
        //只枚举最低位
        int k = __builtin_ctz(i); 
        int j = 1 << k;
        if (dp[i - j] && !(mark[k] & (i - j))) dp[i] = 1;
    }
    for (int i = 0; i < 1 << n; i++) ans += (dp[i] == 1);
    cout << ans; 
    return 0;

}