爆搜
对每一个位置有两种操作:
1.对已有的每一个组进行枚举,看能否放入其中.
2.新建一个组,放入其中.
参考代码
#include<bits/stdc++.h>
const int N=15;
typedef long long ll;
using namespace std;
int n;
int a[N];
int res=1e9;
ll vis[N];
inline ll gcd(ll a,ll b) {
if(b==0)
return a;
return
gcd(b,a%b);
}
inline void dfs(int k,int now) {
if(now==n+1) {
if(k<res)
res=k;
return;
}
for(int i=1; i<=k; i++)
if(gcd(vis[i],a[now])==1) {
vis[i]*=a[now];
dfs(k,now+1);
vis[i]/=a[now];
}
vis[k+1]*=a[now];
dfs(k+1,now+1);
vis[k+1]/=a[now];
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
cin>>a[i];
vis[i]=1;
}
sort(a+1,a+1+n);
dfs(1,1);
printf("%d",res);
return 0;
}
这里的vis是有可能炸的吧,10000^10肯定爆longlong了吧