1655. 分配重复整数

很小，不难想到状压dp，且应该把状态压缩，依次枚举。

有一个需要注意的地方：有时我们设置搜索状态为，表示进入到第个数，顾客的满足状态为，第个数剩余个。这样显然爆空间，无法实现记忆化，因而时间复杂度直接爆炸。

解决这个问题有一个新思路：就是新增状态时，枚举当前状态的补集。因为：显然新增状态不能和现有状态有交集（因为一个人只能被满足一次）。而枚举所有补集作为新增状态，并直接计算的数量能否满足新增状态，就可以直接舍弃掉维度了。从而实现记忆化，稳定时间复杂度。

对记忆化的理解：每一次进入函数，只要给定参数相同，那么函数计算过程中的每一个量都被确定了，意味着确定参数时，函数的结果不会发生变化，那么我们就没有必要在参数相同的时候重新计算了，而是只算一次，然后记住它的结果，下次遇到相同参数时，直接调用。那么记忆化可行的要求就是：函数的返回值只和给的参数有关，参数确定，返回值不变。通常记忆化都会卡在内存不够这一点上。

代码：

class Solution {
public:
	int f[55][1111];
	int n,m,a[100100],b[1010],tot;
	int dfs(int x,int zt){//这个函数的结果只和x和zt有关，因为相同的x和zt进来，经过的流程是一样的，结果自然一样，于是可以记忆化 
		if(f[x][zt]){
			return f[x][zt]==1?1:0;
		}
		if(x==51){
			return (zt==((1<<m)-1))?1:0;
		}
		int ff=0;
		for(int i=0;i<(1<<m);i++){
			if(i&zt) continue;
			int res=0;
			for(int j=0;j<m;j++){
				if(i&(1<<j)){
					res+=b[j];
				}
			}
			if(res>a[x]) continue;
			ff|=dfs(x+1,i|zt); 
		}
		f[x][zt]=ff?1:-1;
		return ff;
	}
    bool canDistribute(vector<int>& nums, vector<int>& quantity) {
        n=nums.size();m=quantity.size();
        sort(nums.begin(),nums.end());
        a[++tot]++;
        for(int i=1;i<n;i++){
        	if(nums[i]!=nums[i-1]) ++tot;
        	a[tot]++;
		}
		for(int i=0;i<m;i++){
			b[i]=quantity[i];
		}
		return dfs(1,0); 
    }
};