状压dp-基础题目1（糖果）

基础题目1解题思路这题的数据规模:1≤N≤1001≤M≤201≤K≤201≤Ti≤M。可以把M种口味用二进制表示比如M5时s00001表示选了第1种口味第2-5种口味没选。我们可以定义dp数组dp[s]表示选了口味集合s二进制编码转成整数需要的最少糖果包数。定义数组tt为n包糖每包糖的口味集合二进制编码转十进制整数。初始化一开始初始化所有dp数组元素为0x3f3f3f3f。之后设置dp[0]0对输入的N包糖的口味做移位和或运算比如样例的第一包口味为112tt[1](00011)b(00011)b(3)d所以dp[3]1第二包口味为1,2,3tt[2](00111)b(00111)b(7)d所以dp[7]1后面第3至6包糖也是这样表示。状态转移外层循环遍历n包糖循环变量为i内层循环遍历所有二进制组合循环变量j从0遍历到(1m)-1。我们先看一下口味集合j是否可以实现即判断dp[j]是否小于0x3f3f3f3f如果是把第i颗糖加入j集合形成新集合j|t[i]。dp[j|t[i]min(dp[j|t[i],dp[j]1)。输出答案如果dp[(1m)-1]0x3f3f3f,输出答案dp[(1m)-1];否则输出-1无法凑出所有口味AC代码#includebits/stdc.husingnamespacestd;intn,m,k,tt[110],dp[122],t[110][25];intmain(){cinnmk;memset(dp,0x3f,sizeof(dp));dp[0]0;for(inti1;in;i){ints0;for(intj1;jk;j){cint[i][j];s(s|(1(t[i][j]-1)));}tt[i]s;dp[s]1;}for(inti1;in;i){for(intj0;j(1m);j){if(dp[j]0x3f3f3f3f){dp[j|tt[i]]min(dp[j|tt[i]],dp[j]1);}}}if(dp[(1m)-1]0x3f3f3f3f)coutdp[(1m)-1];elsecout-1;return0;}