AcWing 1118. 分成互质组
原题链接
简单
作者:
十六
,
2021-01-18 16:53:36
,
所有人可见
,
阅读 299
#include<bits/stdc++.h>
using namespace std;
const int MAX = 10+5;
int n, ans;
int a[MAX];
int g[MAX][MAX];
bool v[MAX];
int gcd(int a, int b){
return b? gcd(b, a%b):a;
}
//gr是当前序列的下标 gc是当前序列中待填数的位置下标
//pos指该从给定数字序列的第几个开始搜索了
//cnt记录已经搜索完的数字个数
//这里搜索的时候只关心能不能向当前序列里面放数字
//一旦开了新的序列,就不再向前面的序列中放数字了
void dfs(int gr, int gc, int pos, int cnt){
if(gr>=ans) return ;
if(cnt==n){
//序列的下标从0开始的,所以要+1
ans = min(ans, gr+1);
return ;
}
//从后面的序列找数字是不是可以放到当前序列中
bool f = true;
for(int i=pos; i<n; i++){
if(v[i]) continue;
bool ff = true;
for(int j=0; j<gc; j++){
if(gcd(g[gr][j], a[i])!=1){
ff = false;
break;
}
}
if(ff){
v[i] = true;
g[gr][gc] = a[i];
dfs(gr, gc+1, i+1, cnt+1);
v[i] = false;
f = false;
}
}
//这里如果有数字可以放到当前序列里面
//就没必要再尝试新开一个序列了
//只有尝试完所有的数字,都不能再放到最后一个队列里面了
//才需要新开一个队列
//起到剪枝的作用
if(f) dfs(gr+1, 0, 0, cnt);
}
int main(){
scanf("%d", &n);
for(int i=0; i<n; i++) scanf("%d", &a[i]);
ans = MAX;
dfs(0, 0, 0, 0);
cout<< ans<< endl;
return 0;
}