题意：

n头牛，d种疾病，每头牛都患一些疾病，现在要求选出最多的牛，使这些牛患病的种类数不超过k。n≤1000，d≤15

题解：

状压dp。f[i][S]表示当前考虑i头牛，患病集合为S，

则f[i][S]=max(f[i+1][S|si]+1,f[i+1][S]),S|si为1的位不超过k且S为1的位不超过k

           =f[i+1][S],S|si为1的位超过k且S为1的位不超过k

可以先对每个状态预处理以下判断它为1的位数是否超过了k。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 40000 6 using namespace std; 7  8 inline int read(){ 9     char ch=getchar(); int f=1,x=0;10     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}11     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();12     return f*x;13 }14 int f[2][maxn],n,d,k,a[maxn/20],x,y; bool no[maxn];15 void init(){16     inc(i,0,(1<
        
         k){no[i]=1; break;}20         }21     }22 }23 int main(){24     n=read(); d=read(); k=read(); init();25     inc(i,1,n){
   int x=read(); inc(j,1,x){
   int y=read(); a[i]|=(1<<(y-1));}}26     x=0; y=1;27     for(int i=n;i>=1;i--){28         inc(j,0,(1<
        
       
      
     

 

20160816