BZOJ 1688 [Usaco2005 Open]Disease Manangement 疾病管理

题目大意

求出一个序列的子集使得它拥有小于k种权值。

这道题首先因为只有15种权值可以DFS求出所有可行情况（当然X种权值包含X-1种权值的情况所以只需要讨论最坏情况就可以了），之后对于每一个元素看它是否包含在这种情况中如果包含就+1.使用状态压缩可以O(1)解决，所以总时间复杂度很低。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,d,k,inx,iny,targ[1000010],f[1000010],tot,ans;
void generate(int pos,int cnt,int now)
{
    if(cnt==k) {targ[++tot]=now;return;}
    if(pos>d) return;
    generate(pos+1,cnt,now);
    now+=1<<pos;
    generate(pos+1,cnt+1,now);
}
void update(int tx)
{
    for(int i=1;i<=tot;++i)
        if((targ[i]|tx)==targ[i])
            f[i]++;
}
int main()
{
    scanf("%d%d%d",&n,&d,&k);
    generate(1,0,0);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&inx);
        int tmp=0;
        while(inx--)
        {
            scanf("%d",&iny);
            tmp+=1<<iny;
        }
        update(tmp);
    }
    for(int i=1;i<=tot;++i) ans=max(ans,f[i]);
    printf("%d\n",ans);
}