本文主要是介绍算法提高之分成互质组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法提高之分成互质组
-
核心思想：dfs
- 枚举每一组可以放哪些元素
-
#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 10;int n;int a[N];int g[N][N];int ans = N;bool st[N];int gcd(int a,int b) //有没有质因数{return b?gcd(b,a%b):a;}bool check(int g[],int x,int start){for(int i=0;i<start;i++){if(gcd(g[i],x) > 1) return false; //如果线性相关}return true;}//当前遍历到哪个组;当前组中该放哪个位置;原数组中从哪个位置开始遍历;已经放好的元素个数void dfs(int gr,int gc,int start,int cnt) {if(gr >= ans) return; //不是更优解if(cnt == n) ans = min(ans,gr);bool flag = true; //记录当前元素(start)是否能放到某一个组中 能放就不开新组for(int i=start;i<n;i++){if(!st[i] && check(g[gr],a[i],gc)) //没用过并且可以放{st[i] = true;g[gr][gc] = a[i]; //放到gc处dfs(gr,gc+1,i+1,cnt+1); st[i] = false; //回溯flag = false; //可以放到某个组中}}if(flag) dfs(gr+1,0,0,cnt); //如果不能放到任何一个组中 开一个新组 同时从0遍历所有元素}int main(){cin>>n;for(int i=0;i<n;i++) cin>>a[i];dfs(1,0,0,0);cout<<ans<<endl;}
这篇关于算法提高之分成互质组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
