[搜索] 质数

题目描述

给定 $n$ 个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？
在满足最少的组数的情况下，使得元素个数最多的那一组的元素个数尽可能的少。

输入格式

第一行 $1$ 个数 $n$。
接下来 $n$ 行，每行 $1$ 个数字表示 $a_i$。

输出格式

一行两个正整数，第一个数是最少的组数，第二个数是满足最少组数的境况下，元素个数最多的那一组的元素个数。

样例

样例输入1：

6
14 
20 
33 
117 
143 
175

样例输出1：

3 2

样例输入2：

4
2 
4 
7 
9

样例输出2：

2 2

数据范围

对于 $30\%$ 的数据，$n\le 8$。
对于 $60\%$ 的数据，$n\le 10$。
对于 $100\%$ 的数据，$n\le 15,1\le a_i\le 10^4$。

题解

由于 $n$ 的范围很小，所以可以直接爆搜。
dfs(int x, vector<int> v, int l1, int l2)，$x$ 表示当前搜到的数的编号，$v$ 表示当前的情况，$l1$ 表示 $ans1$，$l2$ 表示 $ans2$。
如果 $x>n$，说明已经搜完了，更新答案。
否则继续搜索，接下来有两个情况：

• 重新开一个新的组。
• 在现在的组中，找到一个组使得每个数都与其互质，放进去。

接下来进行剪枝：

1. 如果当前的已经比答案差了，直接返回。
2. 还可以进行记忆化，如果搜到第 $i$ 个数的答案已经不比前面搜到的更优，返回。

代码：

int a[20];
bool check(int x, int y){//判断互质
如果 gcd(x, y) 是 1，则互质返回1，否则返回0
}
//组数，每组中最大元素个数
int ans1 = 1e9, ans2 = 1e9;
void dfs(int x, vector<int> v[20], int l1, int l2){
if(l1 > ans1){
return;
}
if(l1 == ans1 && l2 >= ans2){
return;
} 
if(x > n){
if(l1 < ans1){
ans1 = l1;
ans2 = l2;
}
else if(l1 == ans1){
ans2 = min(ans2, l2); 
}
return;
}
vector<int> t[20];
for(int i = 1; i <= l1; ++ i){
for(auto j : v[i]){
t[i].push_back(j);
}
}
----新开一组----
t[l1 + 1].push_back(a[x]);
dfs(x + 1, t, l1 + 1, max(l2, 1));
----从已有的组中选出组放进去----
for(int i = 1; i <= l1; ++ i){
int len = 0, fl = 1;
for(auto j : v[i]){
++ len;
if(check(j, a[x]) == 0){
fl = 0;
break;
}
}
//互质
if(fl){
vector<int> t1[20];
for(int i1 = 1; i1 <= l1; ++ i1){
for(auto j1 : v[i1]){
t1[i1].push_back(j1);
}
}
t1[i].push_back(a[x]);
dfs(x + 1, t1, l1, max(l2, len + 1));
}
}
}
int main(){
输入
vector<int> v[20];
dfs(1, v, 0, 0);
输出
}

原文地址：https://blog.csdn.net/m0_64542522/article/details/142817127

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！