菜鸡的题解005——糖果

数位DP，动态规划（DP）的一种，在本题中表示为使用二进制表示糖果情况，第i位上为0代表第i种糖果不能吃到，为1则代表能吃到。

用a[n]表示在二进制数为n时需要的最少糖果袋数，f[n]表示初始的n个糖果袋的二进制数，定义maxn等于最终的二进制数。

状态转移方程：a[j|f[i]]=min(a[j|f[i]],a[j]+1)
（我用了一个转化为二进制数输出的函数e，可以自己定义一个输出一下，会让本题更加直观）
参考代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<set>
#include<sstream>
#include<cstring>
#include<utility>
using namespace std;
typedef long long ll;
typedef long l;
const int N=1<<20;
int n,m,k,a[N],f[110];
void e(int x){
	for(int i=0;i<20;i++){
		cout<<x%2;
		x/=2;
	}
	cout<<endl;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    int maxn=(1<<m)-1;
    //e(maxn);
    for(int i=0;i<=maxn;i++)a[i]=200;
    for(int i=0;i<n;i++){
    	int x;
    	for(int j=0;j<k;j++){
    		scanf("%d",&x);
    		f[i]|=1<<(x-1);
		}
		a[f[i]]=1;
		//e(f[i]);
	}
	for(int i=0;i<n;i++){
		for(int j=1;j<=maxn;j++){
			if(a[j]!=200){
				a[j|f[i]]=min(a[j|f[i]],a[j]+1);
				//e(j);
				//e(j|f[i]);
			}
		}
	}
	if(a[maxn]==200)cout<<-1;
	else cout<<a[maxn];
}