bzoj1688[Usaco2005 Open]Disease Manangement 疾病管理*

bzoj1688[Usaco2005 Open]Disease Manangement 疾病管理

题意：

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。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 40000
using namespace std;

inline int read(){
    char ch=getchar(); int f=1,x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f*x;
}
int f[2][maxn],n,d,k,a[maxn/20],x,y; bool no[maxn];
void init(){
    inc(i,0,(1<<d)-1){
        no[i]=0; int tot=0;
        for(int j=0;(1<<j)<=i;j++)if(i&(1<<j)){
            tot++; if(tot>k){no[i]=1; break;}
        }
    }
}
int main(){
    n=read(); d=read(); k=read(); init();
    inc(i,1,n){int x=read(); inc(j,1,x){int y=read(); a[i]|=(1<<(y-1));}}
    x=0; y=1;
    for(int i=n;i>=1;i--){
        inc(j,0,(1<<d)-1)if(!no[j]){
            int z=j|a[i]; if(no[z])f[y][j]=f[x][j];else f[y][j]=max(f[x][z]+1,f[x][j]);
        }
        swap(x,y);
    }
    printf("%d",f[x][0]); return 0;
}

20160816