Leetcode状压DP
状压DP，是状态压缩和DP相结合，通常是将某个局面，或某种选择方案视为一个状态，状态与状态进行转移。
涉及一些位运算知识：
for(int i = 0;i < (1<>j)&1 // 判断i的第j位，且可以取值
for(int cur=s; cur>0; cur=(cur-1)&s) // 枚举s的子集
解释一下s的子集枚举，假设s=13，即1101，s的所有子集如下：
1 1 0 1
1 1 0 0
1 0 0 1
1 0 0 0
0 1 0 1
0 1 0 0
0 0 0 1
共\(2^3-1\)个
Leetcode 1879. 两个数组最小的异或值之和
题解：问题模型就是两个数组的带权匹配，可以用状压DP、匈牙利算法KM、随机算法模拟退火。这里只介绍状压DP的做法。
dp[i]表示左边状态为i，右边选择到了第__bulitin_popcount(i)个，递推的时候相当于先算出1的个数为k的状态，在算出1的个数为k+1的状态
class Solution {
public:
int minimumXORSum(vector& nums1, vector& nums2) {
int n = nums1.size(), ans = 0x3f3f3f3f;
int dp[1< n) continue;
for(int j = 0;j < n;j++) {
if(i & (1< Leetcode 2172. 数组的最大与和
题解：把两组数组都扩展到2*m长度，就和上一题一样了
class Solution {
public:
int maximumANDSum(vector& nums, int m) {
int n = nums.size(), ans = 0;
int dp[1<<2*m];
memset(dp, 0, sizeof(dp));
for(int i = 0;i < (1<<2*m);i++) {
int cnt = __builtin_popcount(i); // 1的个数
if(cnt > n) continue;
for(int j = 0;j < 2*m;j++) {
if((i>>j)&1) {
dp[i] = max(dp[i], dp[i^(1< Leetcode 1947. 最大兼容性评分和
题解：同1879
class Solution {
public:
int cal(vector& nums1, vector& nums2) {
int res = 0, n = nums1.size();
for(int i = 0;i < n;i++) res += (1-(nums1[i]^nums2[i]));
return res;
}
int maxCompatibilitySum(vector>& students, vector>& mentors) {
int n = students.size(), ans = 0;
vectordp(1< Leetcode 1595. 连通两组点的最小成本
题解：dp[i][[s]表示左边选择前i个，右边选择s，不过和前面相比，是从dp[i][s]往后推，而不是从前推出dp[i][s]。
class Solution {
public:
int connectTwoGroups(vector>& cost) {
int n = cost.size(), m = cost[0].size();
int dp[n+1][(1< Leetcode 1494. 并行课程 II
题解：把已经上完的课当做一个状态learned，当前状态下可选择的课为wait，枚举wait的子集作为一个选择，所有选择里取最小值。
参考链接：钰娘娘】1494. 并行课程 II 拓扑反例+状态压缩动态规划
class Solution {
public:
int minNumberOfSemesters(int n, vector>& relations, int k) {
int pre[n], dp[1< 0;cur=(cur-1)&wait) { // 枚举wait的一个子集学习
if(__builtin_popcount(cur) > k) continue; // 子集1的个数不能超过k，这个nb!!
dp[learned|cur] = min(dp[learned|cur], dp[learned] + 1);
}
}
return dp[(1<