C++ 状态压缩dp

解题思路:尝试了一下dfs只能拿到一半的分数，刚好昨天学了状压dp，每一包糖果的组合都可以用一种状态来表示。可以枚举每一种状态通过状态转移方程得到结果

注意事项:

参考代码:

#include<bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

int n,m,k;

int dp[1<<20];//达到状态i所需的最少次数

int a[110];//表示每一包糖的状态要开到110 不然会一个点过不去

int main()

{   

    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n>>m>>k;//n包糖果 m种 一包k个

    memset(dp,INF,sizeof(dp));//全都初始化成无穷大

    for(int i=1;i<=n;i++){

        int t=0,p=0;

        for(int j=1;j<=k;j++){

            cin>>p;p--;

            t=t|(1<<p);//存储状态 注意要使用| 而不是 +

        }

        dp[t]=1;//表示这种状态一包即可

        a[i]=t;//记录这包糖的状态

    }

    for(int i=0;i<(1<<m);i++){//枚举状态

        for(int j=1;j<=n;j++){//枚举糖果

            //开始状态转移 |可以看成选择这个糖果

            dp[i|a[j]]=min(dp[i]+1,dp[i|a[j]]);

        }

    }

    if(dp[(1<<m)-1]==INF){//因为状态是从0开始枚举的所以要减个1

        cout<<"-1"<<endl;

    }else{

        cout<<dp[(1<<m)-1]<<endl;

    }

    return 0;

}