题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int a[20];
vector<int> g[20];//s[i]表示某一个组
int cnt,ans=20;//cnt表示当前已分的组数
int gcd(int a,int b)
{
if(!b) return a;
return gcd(b,a%b);
}
bool check(int x,int pos)//判断一个数x是否能放入某一组中,pos表示第pos个组
{
for(int i=0;i<g[pos].size();i++)
{
if(gcd(x,g[pos][i])!=1) return false;
}
return true;//与组内任意一个数都互质
}
void dfs(int u)//u表示当前考虑第u个数
{
if(cnt>=ans) return;//剪枝
if(u==n+1)//n个数已经分好组
{
ans=min(ans,cnt);
return;
}
for(int i=1;i<=cnt;i++)//考虑cnt个组
{
if(check(a[u],i))//可以放入
{
g[i].push_back(a[u]);
dfs(u+1);//考虑下一个数
g[i].pop_back();//回溯
}
}
//考虑完放入原有组,再考虑新开一组
cnt++;//新开一组
g[cnt].push_back(a[u]);
dfs(u+1);//考虑下一个数
g[cnt].pop_back();
cnt--;
}
/*
思路:与小猫爬山类似,也是将若干元素分为若干组,每一组具有某特征,求最小组数
数据量n<=10,,可以考虑暴搜+剪枝,依次考虑每一个元素,先考虑是否能放入已有的
cnt个组中,再考虑放入一个新组中,即每个节点至多有cnt+1个分支(每一个数都要经过
这两个考虑)
*/
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
dfs(1);
cout<<ans;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla