集美大学：矩阵选数零基础讲解-Toy模板网

这篇具有很好参考价值的文章主要介绍了集美大学：矩阵选数零基础讲解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一：集美·大学矩阵选数

本题是一道填空题，选手直接使用代码输出一个数字即可。

牛客集美大学矩阵选数,acm刷题日历,矩阵,算法,数据结构

从以上大小为 13×1313\times 1313×13 的矩阵中选择一些数，选择的数必须满足以下两个条件：

每一行最多有一个数被选择；
每一列最多有一个数被选择。

对选择的数进行求和得到 SumSumSum ，所有可能的选择方案中 SumSumSum 的最大值为多少分分？

输入描述:

无

输出描述:

仅一行，包含一个数字，如题意所示，为 SumSumSum 的最大值。

二：结果代码

void Task(int TestCase) {
    const int n = 13;
    const int m = 1 << n;
    array<array<ll, n>, n> arr;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }

    array<ll, m> dp{};
    for (int i = 0; i < n; i++) {
        array<ll, m> mdp{};
        for (int sta = 0; sta < m; sta++) {
            if (__builtin_popcountll(sta) == i + 1) {
                for (int bit = 0; bit < n; bit++) {
                    if ((sta >> bit) & 1) {
                        mdp[sta] = max(mdp[sta], dp[sta ^ (1 << bit)] + arr[i][bit]);
                    }
                }
            }
        }
        swap(dp, mdp);
    }
    cout << dp[m - 1] << '\n';
}

三：语法点讲解

1：数字左移与右移

const int m = 1 << n;

这个代码的意思是定义常量m的大小为1左移n为，即2的n次方。

2：__builtin_popcountll(sta) == i + 1

这个函数的作用是检查sta中1的个数。

3：dp[sta ^ (1 << bit)]

这个代码是将sta与1左移bit位后的数字进行异或运算（若异则为1，若同为0），具体在这个代码具有将sta的bit位取反的作用。

4： 如何表示13个1的二进制

将1左移13位-1即可。

四：代码具体讲解

 array<ll, m> dp{};
    for (int i = 0; i < n; i++) {
        array<ll, m> mdp{};
        for (int sta = 0; sta < m; sta++) {
            if (__builtin_popcountll(sta) == i + 1) {
                for (int bit = 0; bit < n; bit++) {
                    if ((sta >> bit) & 1) {
                        mdp[sta] = max(mdp[sta], dp[sta ^ (1 << bit)] + arr[i][bit]);
                    }
                }
            }
        }
        swap(dp, mdp);
    }
    cout << dp[m - 1] << '\n';
}

1：首先明白不同i下dp[sta]的含义：

他的含义是在当前i下，sta的范围是0到2^13次方，对于一个固定的sta，知道他的二进制也就知道了他的列的选择，从右往左分别对应着0-12列的选择。

2：dp转化的讲解。

对于给定的i与sta，我们首先要看sta的1的数量是否与i对应，因此有

if (__builtin_popcountll(sta) == i + 1)

注意这里的列为1的个数是i+1而不是i(由于i从0开始)。

挑选出特定的sta后，我们开始状态转移。假设当前的i为4，我们的dp[sta]保存的是i为3的最优解，i加到4后，对于特定的sta我们将sta的任意一列1(if ((sta >> bit) & 1))改为第四行的数（arr[i][j]）（原本的1是是前三行同一列的数）,然后再加上去掉这一列的1的最大值（已经求出）（dp[sta ^ (1 << bit)]），最后再对这些为1的列取最大值就行了，因此有那个max函数。

这里的转化核心就是当对于特定的i和sta(sta的1的个数为i+1),原本的dp[sta]是针对i-1的，对于已经选好的列（由sta的二进制决定），对于sta的每一个j列(j为1)，我们都将这个1选择为arr[i][j]，因此剩余的1的选择的最优值由dp[sta^1<<j]得知，然后对于每个j遍历一次即可获取当前i下dp[sta]的最优解。

最后那个swap函数就是更新dp数组的作用（随着i的增加而更新）。