分成互质组(dfs)题解

本文主要是介绍分成互质组(dfs)题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述:

题目分析：

判断题意大体思路是使用dfs进行深度搜索
1、创建一个分组的数组v
2、对每组进行匹配，如果这个深度的数字符合条件，就将其丢进去，然后回溯。
3、如果没有一组能够符合条件，就将这个数字丢进下一组，并新开一组。

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n;
ll arr[100];
ll v[100];
ll cnt = 0x3f3f3f3f;
ll gcd(ll a, ll b)
{return b == 0 ? a : gcd(b, a % b);
}
void dfs(int k, int step)//k表示的是组数
{if (step == n + 1){if (k < cnt)cnt = k;return;}//把每个数字对每组进行匹配 如果能匹配就放进去 继续深度搜索for (int i = 1; i <= k; i++){if (gcd(v[i], arr[step]) == 1)//如果能够加入这个组{v[i] *= arr[step];//放进去  dfs(k, step + 1);v[i] /= arr[step];//回溯}}v[k + 1] *= arr[step];//放入下一组dfs(k + 1, step + 1);v[k + 1] /= arr[step];
}
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> arr[i];v[i] = 1;//组数}//sort(arr + 1, arr + n + 1); dfs(1, 1);cout << cnt << endl;
}

这篇关于分成互质组(dfs)题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---