赞
踩
给定 n 个正整数,将它们分组,使得每组中任意两个数互质。
至少要分成多少个组?
输入格式
第一行是一个正整数 n。
第二行是 n 个不大于10000的正整数。
输出格式
一个正整数,即最少需要的组数。
数据范围
1≤n≤10
输入样例:
6
14 20 33 117 143 175
输出样例:
3
分析:
d f s 策 略 : dfs策略: dfs策略:
依 次 枚 举 每 个 每 个 正 整 数 a [ u ] , 对 每 个 a [ u ] , 依 次 枚 举 每 一 组 , 判 断 a [ u ] 能 否 放 入 现 有 的 组 中 。 依次枚举每个每个正整数a[u],对每个a[u],依次枚举每一组,判断a[u]能否放入现有的组中。 依次枚举每个每个正整数a[u],对每个a[u],依次枚举每一组,判断a[u]能否放入现有的组中。
具体落实:
v e c t o r 开 二 维 数 组 v e c t o r 来 记 录 每 一 组 对 应 的 数 。 vector开二维数组vector来记录每一组对应的数。 vector开二维数组vector来记录每一组对应的数。
全 局 变 量 a n s 来 更 新 最 少 需 要 的 组 的 数 量 。 全局变量ans来更新最少需要的组的数量。 全局变量ans来更新最少需要的组的数量。
注 意 回 溯 恢 复 现 场 。 注意回溯恢复现场。 注意回溯恢复现场。
代码:
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> using namespace std; const int N=10; int n,a[N]; vector<int> g[N]; int ans=N,len; int gcd(int a,int b) { return b ? gcd(b,a%b) : a; } bool check(int u,int k) //u能否放入第k组 { for(int i=0;i<g[k].size();i++) if(gcd(g[k][i],u)>1) return false; return true; } void dfs(int u) { if(u==n) { ans=min(ans,len); return ; } //看a[u]能够放在哪一组 for(int i=0;i<len;i++) if(check(a[u],i)) { g[i].push_back(a[u]); dfs(u+1); g[i].pop_back(); } //开新组 g[len++].push_back(a[u]); dfs(u+1); g[--len].pop_back(); } int main() { cin>>n; for(int i=0;i<n;i++) cin>>a[i]; dfs(0); cout<<ans<<endl; return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。