這題能不能貪心，是很難說(shuō)的。。
因?yàn)闆](méi)有能什么證明貪心是對(duì)的，但也沒(méi)找到什么反例。
代碼寫(xiě)出來(lái)，WA了。
但總覺(jué)得是對(duì)的，因?yàn)閱岬膶?shí)在找不到反例。
結(jié)果找到數(shù)據(jù)測(cè)了下，果然十個(gè)過(guò)了九個(gè)。。
你看，如果這是NOIP，跟滿分都沒(méi)啥區(qū)別的對(duì)吧。我已經(jīng)滿足了。。
沒(méi)過(guò)的那組，比較大，肉眼看不出是啥問(wèn)題。
想了下，給排序加多了一個(gè)判斷，然后那組數(shù)據(jù)就過(guò)了。。
然后提交，嗎的還上榜了。。無(wú)語(yǔ)。
這樣做比較無(wú)恥，網(wǎng)上有人說(shuō)用最大流做，不理解。下次想一想。
思路：
如果牛喜歡的種類(lèi)個(gè)數(shù)小于 K，那這種牛是無(wú)法滿足的。。
把牛按照喜歡的種類(lèi)個(gè)數(shù)排序，先處理小的。
就是用組合數(shù)枚舉每一種可能的 pizza 情況。
用 hash 保存這些情況。
代碼：
#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 65536
struct cow_node 
{
int val, cnt;
};
int C, T, K, ans;
struct cow_node cows[1024];
int hash[HASH_SIZE];
int cmp(const void *a, const void *b)
{
if (((struct cow_node *)a)->cnt == ((struct cow_node *)b)->cnt)
return ((struct cow_node *)a)->val - ((struct cow_node *)b)->val;
return ((struct cow_node *)a)->cnt - ((struct cow_node *)b)->cnt;
}
inline int insert(int val)
{
int i, h;
h = val & (HASH_SIZE - 1);
for (i = h + 1; i != h && hash[i] && hash[i] != val; )
i = (i + 1) & (HASH_SIZE - 1);
if (i == h || hash[i] == val)
return 0;
hash[i] = val;
return 1;
}
inline int calc(struct cow_node *t)
{
int arr[32], map[32], i, j, val;
for (i = j = 0; i < 32; i++)
if (t->val & (1 << i))
map[j++] = (1 << i);
for (i = 0; i < K; i++)
arr[i] = i;
while (1) {
val = 0;
for (i = 0; i < K; i++)
val |= map[arr[i]];
if (insert(val))
return 1;
for (i = K - 1; i >= 0 && arr[i] == i + t->cnt - K; i--);
if (i < 0)
break;
arr[i]++;
for (i++; i < K; i++)
arr[i] = arr[i - 1] + 1;
}
return 0;
}
int main()
{
int i, j, k;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &C, &T, &K);
for (i = 0; i < C; i++) {
scanf("%d", &cows[i].cnt);
cows[i].val = 0;
for (j = 0; j < cows[i].cnt; j++) {
scanf("%d", &k);
k--;
cows[i].val |= 1 << k;
}
if (cows[i].cnt < K) {
i--; C--;
continue;
}
}
qsort(cows, C, sizeof(cows[0]), cmp);
for (i = 0; i < C; i++)
ans += calc(&cows[i]);
printf("%d\n", ans);
return 0;
}