1460: [蓝桥杯2019初赛]糖果

题目描述

糖果店的老板一共有M 种口味的糖果出售。为了方便描述，我们将M种口味编号1~M。小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是K颗一包整包出售。幸好糖果包装上注明了其中K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。给定N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。

输入

第一行包含三个整数N、M 和K。
接下来N 行每行K 这整数T1,T2,…,TK，代表一包糖果的口味。
1<=N<=100，1<=M<=20，1<=K<=20，1<=Ti<=M。

输出

一个整数表示答案。如果小明无法品尝所有口味，输出-1。

样例输入

6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2

样例输出

2

解题思路

目前使用的方法是图的搜索算法-回溯法，类比0-1背包问题，依次考虑每一包糖果是否购买，并在当前购买包数超过当前最小包数时回溯。
尚未AC：超时！

解题代码

#include <stdio.h>
#include <stdlib.h>int n,m,k;
int num,min;
int cidy[101][21],taste[21],bag[101];void Backtrack(int t);int main()
{while(scanf("%d %d %d",&n,&m,&k)!=EOF){int i,j;min=201;for(i=1; i<=n; i++)for(j=1; j<=k; j++)scanf("%d",&cidy[i][j]);for(i=1; i<=m; i++)taste[i]=0;for(i=1; i<=n; i++)bag[i]=0;Backtrack(1);if(min==201)printf("-1\n");elseprintf("%d\n",min);}
}void Backtrack(int t)
{int i;int flag;if(t>n){flag=1;for(i=1; i<=m; i++){if(taste[i]==0){flag=0;break;}}if(flag==1){num=0;for(i=1; i<=n; i++){if(bag[i]==1)num++;}if(num<min)min=num;}}else{//买第t包糖果bag[t]=1;for(i=1; i<=k; i++)taste[cidy[t][i]]++;flag=1;for(i=1; i<=m; i++){if(taste[i]==0){flag=0;break;}}if(flag==1){num=0;for(i=1; i<=n; i++){if(bag[i]==1)num++;}if(num<min)min=num;}elseBacktrack(t+1);//不买第t包糖果bag[t]=0;for(i=1; i<=k; i++)taste[cidy[t][i]]--;Backtrack(t+1);}
}

目前想法是设置全局变量计算购买数量，避免每次重复计算所购买的糖果，超时原因应该是该算法类似穷举，有待改进，期望能得到大佬指点