1221：分成互质组

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

【输入】

【输出】

【输入样例】

6
14 20 33 117 143 175

【输出样例】

3

解析：深度优先搜索，详见代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[15];//a[i]表示第i个数
int s[15];//s[i]表示第i组目前有几个数
int zu[15][15];//zu[i][j]表示第i组第j个数是多少
int ans;
//求最大公约数
int gcd(int x, int y) {
    if (x % y == 0) return y;
    return gcd(y, x % y);
}
void dfs(int step) {
    if (step > n) {//n个数都安排完了
        int p = 0;
        for(int i=1;i<=n;i++) { //统计有几组有数
            if (s[i]>0){
                p++;
            }else {
                break;
            }
        }
        ans = min(ans, p);//取最小值
        return;
    }
    for (int i = 1; i <= n; i++) {//遍历每一组数
        if (s[i] > 0) {//已经有数的组
            bool flag = 1; //假设a[step]跟第i组数互质
            for(int j = 1; j <= s[i]; j++) {//枚举每个数
                if (gcd(a[step], zu[i][j]) != 1) {//不互质
                    flag = 0;
                    break;
                }
            }
            if (flag == 1) {//都互质
                s[i]++;//加入第i组
                zu[i][s[i]] = a[step];
                dfs(step + 1); //下一步
                s[i]--;//回溯，即从第i组剔除
            }
        } else {//新组（组内没有数）
            s[i]++;//加入第i组
            zu[i][s[i]] = a[step];
            dfs(step + 1); //下一步
            s[i]--;//回溯，即从第i组剔除
            break;//新组只做一次
        }
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    ans = n;//最多n组
    dfs(1);//深搜
    cout << ans;
    return 0;
}