|
|
思路： 这题没有啥好的方法了，看来。用组合C(K, D)枚举所有可能的疾病集合。 其实复杂度很高的，C(15, 7) 都不知道多大了。但是数据比较弱。 用别人的代码试了一下，用STL里面的全排列生成函数，都可以 60ms AC。 下面的代码，没有用STL里面的函数，我以为会快一点，结果慢了不少，200+ms。。 原理就是把16位分成2个8位来处理。
 #include <stdio.h>
  struct table  {
 int cnt, arr[128];
} tbl[] = {
  { 1, {0,} },
{ 8, {1,2,4,8,16,32,64,128,} },
{ 28, {3,5,6,9,10,12,17,18,20,24,33,34,36,40,48,65,66,68,72,80,96,129,130,132,136,144,160,192,} },
{ 56, {7,11,13,14,19,21,22,25,26,28,35,37,38,41,42,44,49,50,52,56,67,69,70,73,74,76,81,82,84,88,97,98,100,104,112,131,133,134,137,138,140,145,146,148,152,161,162,164,168,176,193,194,196,200,208,224,} },
{ 70, {15,23,27,29,30,39,43,45,46,51,53,54,57,58,60,71,75,77,78,83,85,86,89,90,92,99,101,102,105,106,108,113,114,116,120,135,139,141,142,147,149,150,153,154,156,163,165,166,169,170,172,177,178,180,184,195,197,198,201,202,204,209,210,212,216,225,226,228,232,240,} },
{ 56, {31,47,55,59,61,62,79,87,91,93,94,103,107,109,110,115,117,118,121,122,124,143,151,155,157,158,167,171,173,174,179,181,182,185,186,188,199,203,205,206,211,213,214,217,218,220,227,229,230,233,234,236,241,242,244,248,} },
{ 28, {63,95,111,119,123,125,126,159,175,183,187,189,190,207,215,219,221,222,231,235,237,238,243,245,246,249,250,252,} },
{ 8, {127,191,223,239,247,251,253,254,} },
{ 1, {255,} },
 };
int in[1024], N, D, K, ans;
inline int max(int a, int b)
{
return a > b ? a : b;
}
inline int min(int a, int b)
{
return a < b ? a : b;
}
inline void update(int mask)
{
int i, c;
for (c = i = 0; i < N; i++)
if ((in[i] | mask) == mask)
c++;
ans = max(ans, c);
}
inline void put(struct table *t, int limit, int mask)
{
int i;
for (i = 0; i < t->cnt && t->arr[i] < limit; i++)
update(t->arr[i] | mask);
}
int main()
{
int i, j, cnt, val;
freopen("e:\\test\\in.txt","r",stdin);
scanf("%d%d%d", &N, &D, &K);
for (i = 0; i < N; i++) {
scanf("%d", &cnt);
for (val = 0; cnt--; ) {
scanf("%d", &j);
j--;
val |= 1 << j;
 }
in[i] = val;
}
if (D > 8) {
for (i = max(K - 8, 0); i <= min(D - 8, K); i++)
for (j = 0; j < tbl[i].cnt; j++)
put(&tbl[K - i], 256, tbl[i].arr[j] << 8);
} else
put(&tbl[K], 1 << D, 0);
printf("%d\n", ans);
return 0;
}
|