时间戳

首页 > 解决方案 > 位掩码动态规划 - 形成对

c++ - 位掩码动态规划 - 形成对

问题描述

有 n 个男孩和 n 个女孩需要配对。只有当他们兼容时，男孩 i 才会与女孩 j 形成一对。给定它们兼容性的邻接矩阵，找出这些对可以以 1e9+7 为模的方式数。

例子

输入（控制台）：

3
111
101
110

输出（控制台）：

3

n <= 24，Linux 上的时间限制为 0.5 秒。

我提出了一个 ^2*2^n 解决方案，但它超过了 n>20 的时间限制。所以需要一个 *2^n 解决方案，如果可能的话，甚至可能是 2^n。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    static const int mod = 1000000009;
    int n;
    char x;
    scanf("%d", &n);
    vector<vector<int>> b(n);
    vector<int> m(1 << n);
    m[0] = 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
        {
            x = getchar_unlocked();
            x = getchar_unlocked();
            if (x == '1')
                b[i].emplace_back(j);
        }
    for (int i = 0; i < n; ++i)
        for (int j = (1 << n) - 1; j >= 0; --j)
            for (const auto& x : b[i])
                if ((j & (1 << x)) == 0)
                {
                    auto t = j | (1 << x);
                    m[t] += m[j];
                    if (m[t] >= mod)
                        m[t] -= mod;
                }
    cout << m[(1 << n) - 1];
}

标签： c++dynamic-programmingbitmask

解决方案

想象一下，您有示例矩阵：

111
101
110

您正在查看的是要选择的n1 值选择，以便没有包含两个选择的行或列。

有以下三种有效的解决方案：

100    010    001
001    001    100
010    100    010

一种快速计算它们的方法是遍历一行，比如最上面的一行，对于每个 1 值（标记*如下），添加存在的方式数以填充没有选定行和列的子矩阵：（I用-)

*--
-01
-10

我们正在寻找的价值是“01 10方式的数量”

-*-
1-1
1-0

“加上11 10路数”

--*
10-
11-

“加上10 11路数”

现在，您需要缓存“路数”形式的子问题的解决方案11 10。如果你对矩阵进行行/列排序，你就会意识到

“11 10路数”和“11 10路数”是相同的精确值。(1)

而“01 10路数”也是1。所以，1+1+1=3。

因此，您将执行n子问题来查找n-1子问题的值，这将是....1问题。所需的更差缓存大小是 2^n（用于选择不同的行），但排序会使这个小得多。

为了在 0.5 秒内解决 24 大小的问题，您需要高效的结构，例如位模式，以将整行存储在单个 int 中。对于上述方法，我使用单个 std::string 快速解决了一个位置，它在不到 5 秒的时间内随机运行 20x20。所以，你有你的工作被切断了。

您能否说明这是来自哪个竞争性编程网站，我想在优化后检查该解决方案是否通过。:-)

推荐阅读