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

基础题目1

解题思路

这题的数据规模:1≤N≤100，1≤M≤20，1≤K≤20，1≤Ti≤M。可以把M种口味用二进制表示，比如，M=5时，s=00001表示选了第1种口味，第2-5种口味没选。我们可以定义dp数组，dp[s]表示选了口味集合s（二进制编码转成整数）需要的最少糖果包数。定义数组tt为n包糖每包糖的口味集合（二进制编码转十进制整数）。

初始化

一开始，初始化所有dp数组元素为0x3f3f3f3f。之后设置dp[0]=0，对输入的N包糖的口味做移位和或运算，比如样例的第一包，口味为1，1，2，tt[1]=(00011)b，(00011)b=(3)d，所以dp[3]=1；第二包，口味为1,2,3，tt[2]=(00111)b，(00111)b=(7)d，所以dp[7]=1；后面第3至6包糖也是这样表示。

状态转移

外层循环遍历n包糖（循环变量为i），内层循环遍历所有二进制组合，循环变量j从0遍历到(1<<m)-1。我们先看一下口味集合j是否可以实现，即判断dp[j]是否小于0x3f3f3f3f，如果是，把第i颗糖加入j集合，形成新集合j|t[i]。dp[j|t[i]=min(dp[j|t[i],dp[j]+1)。

输出答案

如果dp[(1<<m)-1]<0x3f3f3f,输出答案dp[(1<<m)-1];否则输出-1（无法凑出所有口味）

AC代码

#include<bits/stdc++.h>usingnamespacestd;intn,m,k,tt[110],dp[1<<22],t[110][25];intmain(){cin>>n>>m>>k;memset(dp,0x3f,sizeof(dp));dp[0]=0;for(inti=1;i<=n;i++){ints=0;for(intj=1;j<=k;j++){cin>>t[i][j];s=(s|(1<<(t[i][j]-1)));}tt[i]=s;dp[s]=1;}for(inti=1;i<=n;i++){for(intj=0;j<(1<<m);j++){if(dp[j]<0x3f3f3f3f){dp[j|tt[i]]=min(dp[j|tt[i]],dp[j]+1);}}}if(dp[(1<<m)-1]<0x3f3f3f3f)cout<<dp[(1<<m)-1];elsecout<<-1;return0;}