病毒

題目大意：

有n（1<=n<=1000）頭奶牛，d（1<=d<=15）種病毒，每頭奶牛身上有可能有很多種病毒病毒，每頭奶牛擠出的牛奶是混在一起放的，問最多可以擠多少頭奶牛的牛奶，而且擠出的奶牛中的病毒種數不大于d（1<=k<=d）

Input

題目中的n，d，k
接下來n行，第一個數d_i表示這頭奶牛身上的病毒種數，然后d_i個數表示各個病毒的種類

Output

輸出只有一個數，就是可以擠多少頭奶牛的牛奶

Sample Input

6 3 2 0 1 1 1 2 1 3 2 2 1 2 2 1

Sample Output

5

Hint

【樣例說明】

約翰可以擠編號為1,2,3,5,6的奶牛的牛奶，牛奶中只含兩種病毒(#1和#2)，病毒種數不大于K(2)。

解題思路：

枚舉要不要某種病毒，然后看符合奶牛的有幾頭即可

代碼：

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,d,k,x,y,ans,a[20],b[1005],p[1005][20]; void dfs(int dep,int now)//dep表示第幾個病毒，now表示選了幾個病毒 {if (now>k) return;//不符合條件if (dep>d)//搜完了{int sum=0;for (int i=1;i<=n;++i)//每頭奶牛{sum++;for (int j=1;j<=b[i];++j)//攜帶的病毒種數if (!a[p[i][j]])//是否包含這個病毒{sum--;//不包含就刪掉break;}}ans=max(sum,ans);//取最大值return;}a[dep]=1;//要dfs(dep+1,now+1);a[dep]=0;//不要dfs(dep+1,now); } int main() {scanf("%d %d %d",&n,&d,&k);for (int i=1;i<=n;++i){scanf("%d",&b[i]);for (int j=1;j<=b[i];++j){scanf("%d",&y);p[i][j]=y;//第i頭牛的第j個病毒}}dfs(1,0);printf("%d",ans);//輸出 }

總結

以上是生活随笔為你收集整理的【dfs】病毒（jzoj 1284）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。