LeetCode 1066. 校园自行车分配 II（状态压缩DP）

输入：workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
输出：6
解释：
自行车 0 分配给工人 0，自行车 1 分配给工人 1 。
分配得到的曼哈顿距离都是 3, 所以输出为 6 。

输入：workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
输出：4
解释：
先将自行车 0 分配给工人 0，
再将自行车 1 分配给工人 1（或工人 2），
自行车 2 给工人 2（或工人 1）。
如此分配使得曼哈顿距离的总和为 4。
 
提示：
0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
所有工人和自行车的位置都不相同。
1 <= workers.length <= bikes.length <= 10

class Solution {
	int mindis = INT_MAX;
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int nw = workers.size(), nb = bikes.size(), i, j;
        vector<vector<int>> dis(nw, vector<int>(nb));
        vector<bool> vis(nb, false);
        for(i = 0; i < nw; ++i)
        	for(j = 0; j < nb; ++j)
        		dis[i][j] = abs(workers[i][0]-bikes[j][0])+ abs(workers[i][1]-bikes[j][1]);
        dfs(workers, bikes, vis, dis, 0, 0);
        return mindis;
    }
    void dfs(vector<vector<int>>& workers, vector<vector<int>>& bikes,
    			vector<bool> &vis, vector<vector<int>> &dis, int idx, int distance)
    {
    	if(idx == workers.size())
    	{
    		mindis = min(mindis, distance);
    		return;
    	}
    	for(int i = 0; i < bikes.size(); ++i)
    	{
    		if(vis[i]) continue;
    		vis[i] = true;
            if(distance < mindis)
    		    dfs(workers, bikes, vis, dis, idx+1, distance+dis[idx][i]);
    		vis[i] = false;
    	}
    }
};

class Solution {
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int m = workers.size(), n = bikes.size(), i, j;
        vector<vector<int>> dis(m, vector<int>(n));
        for(i = 0; i < m; ++i)
            for(j = 0; j < n; ++j)
                dis[i][j] = abs(workers[i][0]-bikes[j][0])+ abs(workers[i][1]-bikes[j][1]);
        int M = 1 << m, N = 1 << n;//每个人或者自行车都看成一个二进制位，0还没选，1选了
        vector<vector<int>> dp(M, vector<int>(N, 1000000));
        for(i = 0; i < m; ++i)
            for(j = 0; j < n; ++j)
                dp[1<<i][1<<j] = dis[i][j];
        for(i = 0; i < M; ++i)
            for(j = 0; j < N; ++j)
            {
                int i_ = i, j_ = j;
                m = i&(-i);//二进制数最后一个1代表的数值lowbit
                n = j&(-j);
                while(m > 0)//遍历之前的人的状态
                {
                    dp[i][j] = min(dp[i][j], dp[i-m][j-n]+dp[m][n]);
                                            //i-m表示少了？个1，少了？个人
                                            //j-n表示少了？辆车
                    i_ -= m;//减掉一个人
                    m = i_&(-i_);
                }
                m = i&(-i);//二进制数最后一个1代表的数值lowbit
                n = j&(-j);
                while(n > 0)//遍历之前的车子状态
                {
                    dp[i][j] = min(dp[i][j], dp[i-m][j-n]+dp[m][n]);
                                            //i-m表示少了？个1，少了？个人
                                            //j-n表示少了？辆车
                    j_ -= n;//减掉一辆车
                    n = j_&(-j_);
                }
            }
        return *min_element(dp[M-1].begin(), dp[M-1].end());
    }
};