医院为什么要做门户网站建设/外链推广论坛

题目

题目链接

题解

数位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;
}