分成互质组

题目

信息学奥赛一本通（C++版）在线评测系统 给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？

输入

第一行是一个正整数n。1 ≤ n ≤ 10。

第二行是n个不大于10000的正整数。

输出

一个正整数，即最少需要的组数。

输入样例

6
14 20 33 117 143 175

输出样例

3

思路

如果按之前区间分组的思路, 当此点无法加入到之前的组中, 则自己开一个组。

问题在于怎么维护这几个组。可以使用vector二维数组。

在DFS时, 当前点有n+1种选择, 加入之前的n组（如果可以加的话）, 自己新创一个组。

判断是否互质可以定义一个check函数。

若把每个数当一个节点孩子, 不互质的两个点连一条边表示互相仇恨, 那么就是求该图中互相不仇恨的点分组方案数。最大团问题。

这里数据范围很小, 故不需要考虑那么多。依然是采用决策树的方式来思考。先考虑第一个组, 再考虑第二个组。 考虑第一个组时会一直把能放到第一个组的所有点都放进去, 到第二个组时也是一样。这样在新来点的时候就不需要一次考虑之前所有组, 只需要考虑当前组即可。

一般出成爆搜都是NP完全问题, 否则就会是贪心DP问题。

代码

const int N = 11;
int group[N][N];
int n;
int res = N - 1;
int a[N];
bool st[N];
 
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
 
bool check(int u, int gc, int start)
{
    for (int i = 0; i < gc; i++)
        if (gcd(a[group[u][i]], a[start]) > 1)
            return false;
    return true;
}
 
void dfs(int u, int gc, int tc, int start)
{
    if (u >= res)
        return;
    if (tc == n)
        res = u;
    bool flag = true;
    for (int i = start; i < n; i++)
    {
        if (!st[i] && check(u, gc, i))
        {
            st[i] = true;
            group[u][gc] = i;
            dfs(u, gc + 1, tc + 1, i + 1);
            st[i] = false;
            flag = false;
        }
    }
    if (flag)
        dfs(u + 1, 0, tc, 0);
}
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
 
    dfs(1, 0, 0, 0);
    cout << res << endl;
    return 0;
}