原题链接

题目描述

106号房间共有$n$名居民， 他们每人有一个重要度。房间的门上可以装若干把锁。假设共有$k$把锁，命名为$1$到$k$。每把锁有一种对应的钥匙，也用$1$到$k$表示。钥匙可以复制并发给任意多个居民。每个106房间的居民持有若干钥匙，也就是$1$到$k$的一个子集。如果几名居民的钥匙的并集是$1$到$k$，即他们拥有全部锁的对应钥匙，他们都在场时就能打开房门。新的陆战协定规定，一组居民都在场时能打开房门当且仅当他们的重要度加起来至少为$m$。问至少需要给106号房间装多少把锁。即，求最小的$k$，使得可以适当地给居民们每人若干钥匙(即一个$1$到$k$的子集)，使得任意重要度之和小于$m$的居民集合持有的钥匙的并集不是$1$到$k$，而任意重要度之和大于等于$m$的居民集合持有的钥匙的并集是$1$到$k$。

输入格式

第一行两个整数$n$和$m$，$0<n<21，0<m<1000000001$。
第二行$n$个整数表示居民们的重要度。
重要度在$[1,1000000000]$之间。

输出格式

一个整数表示最少需要多少把锁。

题目分析

当某个集合的重要度的总和没有到达m，但是再加上任意一个人，这个集合的重要度就能满足要求。我们假设这个集合缺少一把钥匙，我们求出所有的这样的集合，使得这些集合都缺少一把不同的钥匙，此时所有满足这样条件的集合数量即为所需要的锁的数量了。
状态压缩枚举集合

代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=21;
ll m,a[N];
int n;
ll f[1<<N];//这个集合的总重要程度
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    ll res=0;
    for(int i=0;i<1<<n;i++)
    {
        bool ok=1;
        for(int j=0;j<n;j++)
            if(!(i>>j&1))
            {
                f[i|1<<j]=f[i]+a[j+1];
                if(f[i|1<<j]<m) ok=0;//说明加上一个人重要程度还是小于m
            }
        if(f[i]<m&&ok) res++;//该集合重要程度小于m而且加上一个集合都大于m
    }
    cout<<res<<endl;
    return 0;
}

参考题解 要加油哦~