资源限制

内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

问题描述

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

输入格式

　　第一行包含三个整数 N、M 和 K。
　　接下来 N 行每行 K 这整数 T₁, T₂, · · · , TK，代表一包糖果的口味。

输出格式

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

样例输入

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

样例输出

2

评测用例规模与约定

　　对于 30% 的评测用例，1 ≤ N ≤ 20 。
　　对于所有评测样例，1 ≤ N ≤ 100，1 ≤ M ≤ 20，1 ≤ K ≤ 20，1 ≤ Ti ≤ M。

思路

看到m的数据范围，第一反应这是很明显的状压dp或者暴搜。然而我却首先尝试了暴搜，只过了一个点其他点全超时了......

所以还是状压dp方便和容易理解。

而了解状压dp需要有一些位运算基础。可以戳这里了解。

暴搜10分代码

Code

#include
using namespace std;
int n,m,k;
int a[30];//a[i]记录第i包糖的糖种类情况 
int b[30];
bool buy[30];
int max1,flag=1,cnt=0x3f3f3f,s;
void setbit(int &x,int y){x|=1<<(y-1);//有第3种糖果，y=3//1<<(3-1)后，变成比特位除了第3位是1外其他位都为0 //而|0是不变的，|1则变1 
}
int getbit(int &x,int y){//获得x的第y个比特位 此函数此处没用，反正当时一口气就打完暴搜代码了没管那么多... return (x>>(y-1)&1);//如110 获得第二位,右移2-1位置,变101,再&1
//&1其他位都为0,最后一位若是1则结果为1,否装为0。	
}
void dfs(int x,int y,int now,int ts){//打算买x包,y是买的上一包的编号,现在已经尝试买了now包 ,现在的状态是ts if(now>=cnt)return ;if(now==x&&ts!=s)return ;if(ts==s){//k达到全集cnt=min(cnt,now);return ;}
for(int i=1;i<=n;i++){if(!buy[i]){//没买过 buy[i]=1;dfs(x,i,now+1,a[i]|ts);buy[i]=0;}
}	 }
int main(){int t=0;scanf("%d%d%d",&n,&m,&k);s=(1<flag){max1=__builtin_popcount(a[i]);flag=i;}} if(max1==m){printf("1");exit(0);}for(int i=1;i <=n;i++){for(int j=2;j<=n;j++){//枚举买的包数 buy[i]=1; dfs(j,i,1,a[i]);//买j包,当前买了1包 即第i包 buy[i]=0;}}if(cnt!=0x3f3f3f)printf("%d",cnt);else printf("-1");
return 0;
}

状压dpAC代码

Code 

#include 
using namespace std;
const int N=105,M=(1<<20)+10;
int n,m,k,x,a[N],dp[M];
// dp[i]表示组成i状态的所需的最小包数
int main() 
{cin>>n>>m>>k; memset(dp,-1,sizeof(dp));for(int i=1;i<=n;i++){int s=0;for(int j=1;j<=k;j++){cin>>x;s|=(1<<(x-1)); //因为|0不变，|1变1，所以此循环下来，s有糖果的对应比特位为1 }dp[s]=1;//表示此状态只需要此包便可 a[i]=s;//第i包的状态是s}for(int i=1;i<=n;i++){for(int j=0;j<(1<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！