P4911 工作分配问题（提高）

解题思路

第一步，理解题意。 有n个人和n项工作，每个人只能做一项工作，每项工作也只能由一个人做。第i个人做第j项工作能得到的收益是a[i][j]。我们要安排一种一人一项、一项一人的方案，使所有人的总收益最大。比如样例n=5时，最优安排总收益是50。

第二步，用二进制记录工作分配情况。 n最大只有20，可以用一个二进制数mask表示哪些工作已经被分配：mask的第j位是1就表示第j项工作已经被某人做了。这样的状态一共有2的n次方个，n=20时约100万个，完全存得下。

第三步，确定DP的含义。 定义dp[mask]表示安排好了mask里这些工作（也就是安排好了前面若干个人）能获得的最大总收益。mask里1的个数正好等于已经安排的人数，所以当1的个数是cnt时，就轮到第cnt个人（从0开始数）来选工作。

第四步，写出转移方程。 从mask中去掉一位j，得到上一个状态mask去掉j，那个人做工作j的收益是a[第cnt个人][j]。所以dp[mask]等于max( dp[mask去掉j] + a[cnt-1][j] )，其中j遍历mask里的每一个1。从小到大枚举所有mask，保证算dp[mask]时更小的状态都已算好。

第五步，得到答案。 当所有工作都被分配完，即mask等于(1<<n)-1时，dp的值就是最大总收益。这个DP保证一人一项、一项一人，因为mask的1的个数恰好等于人数。例如样例n=5，最终答案是50。

参考代码

// 工作分配：状态压缩DP，dp[mask]表示前若干人完成mask中这些工作时的最大总收益
#include <iostream>
using namespace std;
int a[25][25];
int dp[1 << 20];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> a[i][j];
    int full = 1 << n;
    dp[0] = 0;
    // 从小到大枚举所有状态
    for (int mask = 1; mask < full; mask++) {
        // 数出mask中已经分配了几份工作，得到当前轮到第几个人
        int cnt = 0, m = mask;
        while (m) { cnt++; m &= m - 1; }
        int r = cnt - 1; // 第r个人(从0开始数)
        int best = -1;
        // 枚举这份工作j：由第r个人来做，从去掉j的状态转移
        for (int j = 0; j < n; j++) {
            if (mask & (1 << j)) {
                int v = dp[mask ^ (1 << j)] + a[r][j];
                if (v > best) best = v;
            }
        }
        dp[mask] = best;
    }
    cout << dp[full - 1] << endl;
    return 0;
}

复杂度分析

状态总数是2的n次方，每个状态要枚举n个工作，所以总时间复杂度O(n·2^n)。n最大是20，20×2^20约2000万次运算，运行很快。dp数组大小是2^n个int，约4MB内存，放在全局数组里没有问题。这个做法比纯搜索剪枝更快更稳定，不会因为数据特殊而超时。