这题通过组合方式来枚举,可以避免组内冗余,但是无法避免不同组之间的冗余,为避免后者,可以加一个判断来避免冗余:
if (gcnts == 0) return;
完整代码:
#include <iostream> #include <algorithm> #include <vector> using namespace std; int n; const int N = 15; int a[N], ans = 20; int mygroups[N][N]; bool vis[N]; int gcd(int x, int y) { return y ? gcd(y, x % y) : x; } bool check(int gn[], int targets, int gcnts) { for (int i = 0; i < gcnts; i++) if (gcd(gn[i], targets) > 1) return 0; return 1; } void dfs(int groups, int cnt, int startf, int gcnts) { if (groups >= ans) return; if (cnt == n) { ans = groups; return; } bool flag = 1; for (int i = startf; i < n; i++) { if (!vis[i] && check(mygroups[groups], a[i], gcnts)) { flag = 0; vis[i] = 1; mygroups[groups][gcnts] = a[i]; dfs(groups, cnt + 1, i + 1, gcnts + 1); vis[i] = 0; if (gcnts == 0) return; } } if (flag) dfs(groups + 1, cnt, 0, 0); } int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } dfs(1, 0, 0, 0); cout << ans << endl; return 0; }
具体地说:例如一共有四个数3,9,2,4
最终的分组为{3,9}{2,4}
如果不加上这个新剪枝,会在枚举出这个分组之后,又枚举出{2,4}{3,9} 明明是等效的,只是改变了相对顺序而已,会浪费我们的搜索时间。
最终的效果是:总时间从600+ms缩减到10+ms
标签:分成,cnt,return,gcnts,int,vis,groups,1118,互质 From: https://www.cnblogs.com/smartljy/p/17808675.html