题目描述
blablabla
样例
blablabla
// 看到了打卡代码评论区大佬的优化。尝试对其的优化进行解释。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 10;
int n;
int p[N];
int group[N][N];
bool st[N];
int ans = N;
int gcd(int a , int b){
return b ? gcd(b , a % b) : a;
}
bool check(int group[] , int gc , int i){
for(int j = 0 ; j < gc ; j ++)
if(gcd(p[group[j]] , p[i]) > 1)
return false;
return true;
}
void dfs(int g , int gc , int tc , int start){// 搜第几组,组内有几个元素,当前一共搜了几个元素,当前组从哪个下标开始搜
if(g >= ans) return;
if(tc == n) ans = g;
bool flag = true;
for(int i = start ; i < n ; i ++){
if(!st[i] && check(group[g] , gc , i)){
st[i] = true;
group[g][gc] = i;
dfs(g , gc + 1 , tc + 1 , i + 1);
st[i] = false;
flag = false;
if(gc == 0) return;// 见注释1
}
}
if(flag) dfs(g + 1 , 0 , tc , 0);
}
int main(){
cin >> n;
for(int i = 0 ; i < n ; i ++) cin >> p[i];
dfs(1 , 0 , 0 , 0);
cout << ans << endl;
return 0;
}
// 代码思路来源:yxc , AC_
// 注释1:如果当前撤销的元素是组中的最后一个元素,就不必再尝试放入任何元素。
// 当撤销的元素为某一组的最后一个元素,那么接下来继续分组的搜索一定无效
// 比如说有{1,2,3}和{4}这两个组。
//如果这两个组都被撤销,接下来无论如何搜索,都会因为2和4两个非互质元素而被分为两个与之前等效的组。