杭州网站建设宣盟网络百度无广告搜索引擎
1243. 糖果
糖果店的老板一共有 M种口味的糖果出售。
为了方便描述,我们将 M种口味编号 1∼M。
小明希望能品尝到所有口味的糖果。
遗憾的是老板并不单独出售糖果,而是 K颗一包整包出售。
幸好糖果包装上注明了其中 K颗糖果的口味,所以小明可以在买之前就知道每包内的糖果口味。
给定 N包糖果,请你计算小明最少买几包,就可以品尝到所有口味的糖果。
输入格式
第一行包含三个整数 N,M,K。
接下来 N行每行 K个整数 T1,T2,⋅⋅⋅,TK,代表一包糖果的口味。
输出格式
一个整数表示答案。
如果小明无法品尝所有口味,输出 −1。
数据范围
1≤N≤100,
1≤M,K≤20,
1≤Ti≤M
输入样例:
6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2
输出样例:
2
状态压缩dp
状态压缩dp用位运算实现。
思路:
dp[ i ][ j ]表示前 i 袋糖果集齐 j 种糖果所需要的最少袋数。
可以选择第 i 袋或者不选择第 i 袋。
状态转移方程为:
dp[ i ][ j ]=min( dp[ i - 1 ][ j ] , dp[ i - 1 ][ j & (~ w[ i ])]+1 )
前面那个是不选择第 i 袋,比较好理解,后面那个可以举个例子
例如我们想要 j 为11011,而w[ i ]为 11100,取反后为00011,11011 & 00011 = 10000,故是从10000这个状态转移过来的。
然后要先预处理dp数组为100,dp[0]=0就可以了。
#include<bits/stdc++.h>
using namespace std;
int w[100],dp[1<<20];
int main()
{int n,m,k;cin>>n>>m>>k;int s=(1<<m)-1;for(int i=1;i<=n;i++){for(int j=1;j<=k;j++){int r;cin>>r;w[i]|=1<<r-1;}}for(int i=1;i<(1<<m);i++) dp[i]=100;dp[0]=0;for(int i=1;i<=n;i++){for(int j=(1<<m)-1;j>0;j--){dp[j]=min(dp[j],dp[j&(~w[i])]+1);}}(dp[s]==100)?(cout<<-1<<endl):(cout<<dp[s]<<endl);return 0;
}