蓝桥杯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
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n, m, k, x, a[N], f[1 n >> m >> k;
	
	memset (f, 0x3f, sizeof f);
	
	for (int i = 0;i  x;
			a[i] |= (1