[数据结构与算法]蓝桥杯2019年第十届省赛真题-糖果

题目

题目链接

题解

数位DP。

a[i]表示第i包糖果的状态；
f[i]表示i这种状态所需的最少糖果包数。

状态就是指一串二进制，最低位表示是否能吃到第1种糖果，次低位表示是否能吃过第2种糖果。

转移方程：f[j | a[i]] = min (f[j | a[i]], f[j] + 1)含义是j | a[i]这种选了第i包糖果的状态所需的最少糖果包数为构成状态j的最少包数+1。
s1 | a[i]表示没有拿第i糖果所能吃到的糖果的状态，与a[i]按位或实现将s2在a[i]中是1的位置上的数变为1，相当于将第i包糖果中的糖果添加到手中，当然，只是种类。

初始化：每个单独一包的糖果都初始化为1，f[a[i]] = 1，其他状态均初始化为无穷大。

（感觉转移方程左边是索引值为表达式的好少见，第一次见）

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n, m, k, x, a[N], f[1<<21];
int main()
{
	
	cin >> n >> m >> k;
	
	memset (f, 0x3f, sizeof f);
	
	for (int i = 0;i < n;i ++) {
		for (int j = 0;j < k;j ++) {
			cin >> x;
			a[i] |= (1 << (x-1)); // 二进制表示每一种糖果是否能吃到 
		}
		f[a[i]] = 1; // 初始化 	
	}
		
	for (int i = 0;i < n;i ++) 
		for (int j = 0;j < (1<<m);j ++)
			f[j | a[i]] = min (f[j | a[i]], f[j] + 1);
	
	int ans = f[(1 << m) - 1];
	if (ans == INF) puts ("-1");
	else cout << ans << endl;
		
	return 0;
}