方法一 IDA*
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define TS int T;cin>>T;while(T--)
#define INPUT freopen("input.txt","r",stdin);
#define OUTPUT freopen("ouput.txt","w",stdout);
using namespace std;
/*
DFS
1.迭代加深: 1层行不行,2层行不行....m层(选多少列,即从包含某种口味糖果的所有行里选)
2.可行性剪枝:估价函数h(),用于估计达到目标状态,至少还需要选多少行(包糖果)
这里是从还没有选择的列中,将所有能选的行看作一行,然后更新状态,看看最少要多少列(即还要多少层)
才能达到目标状态,如果剩余能选的层数小于估价,那么失败,直接返回
3.DFS每次从能够选最少的行数的列开始,这样递归的分叉会少一点。
这里因为M<=20,所以每行(一包糖果)包括多少列(口味)用二进制表示
*/
vector<int> col[20];
int log2[1 << 20];
int n, m, k;
void init_log2()
{
for(int i = 0; i < m; i ++) log2[1 << i] = i;
}
int lowbit(int x)
{
return x & -x;
}
int h(int state)//估价函数
{
int res = 0;
for(int i = (1 << m) - 1 - state; i; i -= lowbit(i))//异或也可以
{
int c = log2[lowbit(i)];
for(auto row : col[c])
state |= row;
// i = i & ~row;//row是取的,取反1就是没取的,&i就表示只留下都没取得
res ++;
if((1 << m) - 1 == state) break;//其实这么整也可以,反正m就30一样的
}
return res;
}
bool dfs(int depth, int state)//层数和当前状态
{
//可行性剪枝
if(depth == 0 || depth < h(state))//层数为0或者需要的最少层数大于剩余层数
return state == (1 << m) - 1;//判断一下搜索是否成功
//优化,从能选最少状态数的开始选,如何枚举没有选的口味?
//这里采用2进制lowbit得到二进制数最末尾的1和后面的0代表的数
//我们将满状态(1 << m) - 1减去(或者异或)当前状态state
//得到的数的二进制中1就代表了哪些位置没选
//每次减去lowbit就可以得到每一位1的位置,此时就用到log2数组得到位置
int t = -1;//可选最少的哪一个口味
for(int i = ((1 << m) - 1) ^ state; i; i -= lowbit(i))//二进制异或其实和减一样的
{
int c = log2[lowbit(i)];
if(t == -1 || col[t].size() > col[c].size()) t = c;//得到可选状态数最少的口味下标
}
for(auto row : col[t])//dfs第t种口味能选的每一种状态
if(dfs(depth - 1, state | row)) return true;//有一次成功就搜索成功
return false;
}
int main()
{
cin >> n >> m >> k;
init_log2();
for(int i = 0; i < n; i ++)
{
int state = 0;//用来记录每包糖果的口味
for(int j = 0; j < k; j ++)
{
int c;
cin >> c;//糖果口味
state |= 1 << (c - 1);//改成从0开始,方便下面操作
}
//现在我们得到了第i包糖果的状态,将每种包含的口味集合里加上这一包糖果
for(int j = 0; j < m; j ++)
{
if(state >> j & 1)//如果该包糖果包含口味m
col[j].push_back(state);//这样就可以得到每种口味有多少包糖果包含它
}
}
//2022.3.29更新 优化一下col数组,把col数组里重复的状态去掉,(为什么快这么多啊???)
for(int i = 0; i < m; i ++)
{
auto &h = col[i];
h.erase(unique(h.begin(), h.end()), h.end());
}
//下面开始DFS 首先是迭代加深
int depth = 0;
while(depth <= m && !dfs(depth, 0)) depth ++;//层数递增尝试
if(depth > m) cout << "-1\n";//层数超过m层,说明搜索失败
else cout << depth << '\n';
return 0;
}
方法2 状态压缩DP
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define TS int T;cin>>T;while(T--)
#define INPUT freopen("input.txt","r",stdin);
#define OUTPUT freopen("ouput.txt","w",stdout);
using namespace std;
const int N = 101, M = (1 << 20) + 5, INF = 100;
//状态压缩DP
int f[M], c[N];//f表示到某一种状态需要最少的糖果包数,c表示每包糖果包含的口味(二进制表示)
int n, m, k;
int main()
{
IOS
cin >> n >> m >> k;
for(int i = 0; i < n; i ++)
for(int j = 0; j < k; j ++)
{
int x;
cin >> x;
c[i] |= 1 << (x - 1);//每包糖果包含的口味状态,这里-1方便枚举
}
//DP
for(int i = 1; i < 1 << m; i ++) f[i] = INF;//初始化
f[0] = 0;//一种口味都没有情况最少是0包糖果
for(int i = 0; i < n; i ++)
{
//f[c[i]] = 1;因为枚举状态时j=0的情况等价于f[c[i]] = 1,所以可以不用
for(int j = (1 << m) - 1; j >= 0; j --)
//为什么要倒着来,是怕当前更新了的状态又去更新同一层其他状态((j | c[i]) >= j,大的状态是用小的更新的)
//也可以用滚动数组,就不用管顺序
//f[j | c[i]] = min(f[j | c[i]], f[j] + 1);
f[j] = min(f[j], f[j & ~c[i]] + 1);
}
/*
也有另一种计算方式,就是类似01背包,判断当前这包糖果i选不选
f[j] = min(f[j], f[j & ~c[i]])
当我们枚举到状态j时,如果不选这包糖果,那么f[i][j]不变
如果选择这包糖果,那么代价就是 f[i - 1][j & ~c[i]] + 1
j & ~c[i] 就是从j里去掉j和c[i]的交集 也就是 j ^ (j & c[i])
但是实际上我感觉这种做法正确性不太好证明 如 1101|0011 = 1111 然而 1111&(~0011) = 1100
尝试一下输出最后的dp序列
方法1
0 100 100 1 100 1 100 1 100 100 100 100 100 100 100 100
100 100 100 1 100 100 1 2 100 100 1 2 100 100 2 2
方法2
0 1 1 1 1 1 1 1 1 2 1 2 2 2 2 2
1 1 1 1 1 2 1 2 1 2 1 2 2 2 2 2
可以发现方法一有些状态是取不到的,这是符合真实情况的
而方法2得到的结果似乎只能保证能够取到的情况的答案是正确的
*/
if(f[(1 << m) - 1] == INF) cout << "-1\n";
else cout << f[(1 << m) - 1] << '\n';
return 0;
}
厉害,很正确