内蒙古自治区建设厅网站,工信部个人备案网站可信吗,扬中网站建设 优帮云,xyz域名的网站有哪些1243. 糖果
糖果店的老板一共有 M种口味的糖果出售。
为了方便描述#xff0c;我们将 M种口味编号 1∼M。
小明希望能品尝到所有口味的糖果。
遗憾的是老板并不单独出售糖果#xff0c;而是 K颗一包整包出售。
幸好糖果包装上注明了其中 K颗糖果的口味#xff0c;所以小…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数组为100dp[0]0就可以了。
#includebits/stdc.h
using namespace std;
int w[100],dp[120];
int main()
{int n,m,k;cinnmk;int s(1m)-1;for(int i1;in;i){for(int j1;jk;j){int r;cinr;w[i]|1r-1;}}for(int i1;i(1m);i) dp[i]100;dp[0]0;for(int i1;in;i){for(int j(1m)-1;j0;j--){dp[j]min(dp[j],dp[j(~w[i])]1);}}(dp[s]100)?(cout-1endl):(coutdp[s]endl);return 0;
}
