蓝桥OJ 2942数字王国之军训排队 DFS剪枝

 蓝桥OJ 2942数字王国之军训排队

#include<bits/stdc++.h>
using namespace std;const int N = 15;//最多10队
int a[N], n;
vector<int>v[N];//二维数组 v[i]记录队伍i中所有人的编号bool dfs(int cnt, int dep)
{if (dep == n+1){//判断合法性for (int i = 1; i <= n; i++){for (int j = 0; j < v[i].size(); j++){for (int k = j + 1; k < v[i].size(); k++){if (v[i][k] % v[i][j] == 0) return false;}}}return true;}//枚举每个人所属的队伍for (int i = 1; i <= cnt; i++){v[i].push_back(a[dep]);if (dfs(cnt,dep+1))return true;v[i].pop_back();}return false;
}
int main()
{cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);//因为n的范围比较小,所以可以从小到大遍历出最少可以分成的队伍for (int i = 1; i <= n; i++){if (dfs(i, 1)){cout << i << '\n';break;}}return 0;
}

上面的方法有一个测试点出现了超时,所以下面用剪枝修改  

#include<bits/stdc++.h>
using namespace std;const int N = 15;//最多10队
int a[N], n;
vector<int>v[N];//二维数组 v[i]记录队伍i中所有人的编号bool dfs(int cnt, int dep)
{if (dep == n+1) return true;//枚举每个人所属的队伍for (int i = 1; i <= cnt; i++){bool tag = true;for (const auto& j : v[i]){if (a[dep] % j == 0){tag = false;break;}}if (!tag)continue;v[i].push_back(a[dep]);if (dfs(cnt,dep+1))return true;v[i].pop_back();}return false;
}
int main()
{cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);//因为n的范围比较小,所以可以从小到大遍历出最少可以分成的队伍for (int i = 1; i <= n; i++){if (dfs(i, 1)){cout << i << '\n';break;}}return 0;
}