【dfs】病毒(jzoj 1284)

病毒

题目大意:

有n(1<=n<=1000)头奶牛,d(1<=d<=15)种病毒,每头奶牛身上有可能有很多种病毒病毒,每头奶牛挤出的牛奶是混在一起放的,问最多可以挤多少头奶牛的牛奶,而且挤出的奶牛中的病毒种数不大于d(1<=k<=d)

Input

题目中的n,d,k
接下来n行,第一个数d_i表示这头奶牛身上的病毒种数,然后d_i个数表示各个病毒的种类

Output

输出只有一个数,就是可以挤多少头奶牛的牛奶

Sample Input

16 3 2 20 31 1 41 2 51 3 62 2 1 72 2 1 8 9

Sample Output

15 2 3

Hint

【样例说明】

约翰可以挤编号为1,2,3,5,6的奶牛的牛奶,牛奶中只含两种病毒(#1和#2),病毒种数不大于K(2)。

解题思路:

枚举要不要某种病毒,然后看符合奶牛的有几头即可

代码:

1#include<cstdio> 2#include<cstring> 3#include<iostream> 4using namespace std; 5int n,d,k,x,y,ans,a[20],b[1005],p[1005][20]; 6void dfs(int dep,int now)//dep表示第几个病毒,now表示选了几个病毒 7{ 8 if (now>k) return;//不符合条件 9 if (dep>d)//搜完了 10 { 11 int sum=0; 12 for (int i=1;i<=n;++i)//每头奶牛 13 { 14 sum++; 15 for (int j=1;j<=b[i];++j)//携带的病毒种数 16 if (!a[p[i][j]])//是否包含这个病毒 17 { 18 sum--;//不包含就删掉 19 break; 20 } 21 } 22 ans=max(sum,ans);//取最大值 23 return; 24 } 25 a[dep]=1;//要 26 dfs(dep+1,now+1); 27 a[dep]=0;//不要 28 dfs(dep+1,now); 29} 30int main() 31{ 32 scanf("%d %d %d",&n,&d,&k); 33 for (int i=1;i<=n;++i) 34 { 35 scanf("%d",&b[i]); 36 for (int j=1;j<=b[i];++j) 37 { 38 scanf("%d",&y); 39 p[i][j]=y;//第i头牛的第j个病毒 40 } 41 } 42 dfs(1,0); 43 printf("%d",ans);//输出 44} 45 46

代码交流 2021