NC206910. 集卡
描述
输入描述
第一行有一个整数T（ 1 ≤ T ≤ 10 ）表示共有T组测试样例
接下来每组的第一行有三个整数n，m，k（ 1 ≤ n ≤ 100 , 1 ≤ m ≤ 17 , 1 ≤ k ≤ 17 ）
n-卡包数
m-总卡牌种类数
k-卡包中的卡牌张数
接下来的n行，每行有k个整数，a1，a2 ··· ak ( 1 ≤ ai ≤ m ) 代表一个卡包中每张卡的卡牌种类。
输出描述
一个整数表示最小数量，如果小明无法集齐所有卡牌，输出-1。
示例1
输入:
2 7 8 4 1 3 5 7 2 4 6 7 8 7 6 5 4 3 2 1 8 8 8 8 2 3 5 7 1 8 8 8 1 2 1 1
输出:
2 -1
C++11(clang++ 3.9) 解法, 执行用时: 192ms, 内存消耗: 8808K, 提交时间: 2020-06-07 13:03:34
#include <iostream>
#include <cstring>
using namespace std;
int T,n,m,k;
long long a[110],f[1<<20];
int main()
{
cin>>T;
while(T--)
{
cin>>n>>m>>k;
memset(a,0,sizeof(a));
memset(f,127,sizeof(f));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
int x;
cin>>x;
a[i]=a[i] | (1<<(x-1));
}
f[a[i]]=1;
}
for(int i=1;i<=(1<<m)-1;i++)
for(int j=1;j<=n;j++)
{
long long k=i|a[j];
if(f[k]>f[i]+1) f[k]=f[i]+1;
}
if(f[(1<<m)-1]>100) cout<<-1<<endl;
else cout<<f[(1<<m)-1]<<endl;
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 292ms, 内存消耗: 1100K, 提交时间: 2020-06-08 20:08:52
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f;
int dp[1<<17];
int main(){
int t;
cin>>t;
for(int ii=0;ii<t;ii++){
int n,m,k;
cin>>n>>m>>k;
memset(dp,inf,sizeof dp);
int flag=dp[0];
dp[0]=0;
for(int i=0;i<n;i++){
int p=0;
for(int j=0;j<k;j++){
int x;
cin>>x;
p|=1<<(x-1);
}
for(int j=0;j<1<<m;j++){
dp[j|p]=min(dp[j|p],dp[j]+1);
}
}
if(dp[((1<<m)-1)]==flag)cout<<"-1"<<endl;
else{
cout<<dp[(1<<m)-1]<<endl;
}
}
return 0;
}