AcWing 1118. 分成互质组
原题链接
简单
作者:
头发没了还会再长
,
2022-04-01 21:40:41
,
所有人可见
,
阅读 150
当dfs求图中一个点到另一个点(需要保证每个点只遍历一次) 不需要回溯
当从图的一种状态到另一种状态有多少种状态(比如棋盘) 需要回溯
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=10;
int n;
int p[N];
bool st[N];
int group[N][N];//存的是下标 表示当前第i组 的第j个数是 p[group[i][j]]
int ans=N;
int gdc(int a,int b){
return b?gdc(b,a%b):a;
}
bool check(int group[],int gc,int j){
for(int i=0;i<gc;i++)
if(gdc(p[group[i]],p[j])>1)
return false;
return true;
}
void dfs(int g,int gc,int tc,int start )//第几组 组内几个元素(下标是什么) 当前一共搜了多少元素 这组从几号下标开始搜
{
if(g>=ans) return;
if(tc==n) ans=g;//tc表示当前分组完成的数的个数
bool flag=true;
for(int i=start;i<n;i++)
if(!st[i] && check(group[g],gc,i)){//当前组内所有的元素和第i个数是互质的
st[i]=true;
group[g][gc]=i;
dfs(g,gc+1,tc+1,i+1);
st[i]=false;
flag=false;
}
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;
}