acwing1118. 分成互质组

题目

题解

判断当前这个数是否可以与前面每个组的数是否互质，是的话就将这个数放入到这个组中，或者就新开一个组来存放这个数。

used表示当前所有组的索引，从0开始计数

#include<iostream>
#include<vector>
using namespace std;
const int N=15;
int nums[N];
int n,ans=N;
vector<int> g[N];
int gcb(int a,int b){
    
    return b?gcb(b,a%b):a;
}
bool check(vector<int> &vec,int x){
    for(int i=0;i<vec.size();i++){
        if(gcb(vec[i],x)>1)return false;
    }
    return true;
}
void dfs(int u,int used){
    if(used+1>=ans)return;//所有组加起来比ans还大就不需要再继续了
    if(u>=n){//将所有数字全部放入后结束
        ans=min(ans,used+1);
        return ;
    }
    for(int i=0;i<=used;i++){//将nums[u]分别放到used个数组
        if(check(g[i],nums[u])){
            g[i].push_back(nums[u]);
            dfs(u+1,used);
            g[i].pop_back();
        }
    }
    if(used+1<=n){//新开一个组
        g[used+1].push_back(nums[u]);
        dfs(u+1,used+1);
        g[used+1].pop_back();
    }
    
    
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>nums[i];
    dfs(0,0);
    cout<<ans<<endl;
    
    return 0;
    
}