题意： 有\(n\)个问题，每个问题的难度为\(a_i\)，最多选出三个问题\(x, y, z\)，要求\(两两之间不能存在整除关系\)， 求最多能获得多大难度的问题集，一个问题集的难度为集合里面所有问题难度的总和。
思路： 考虑从小到大枚举一个数，然后用set维护加入的数，对于一个数\(x\)，去掉它的所有因数，去找最大的那个\(y\)，然后去掉\(y\)的所有因数，再找一个最大的\(z\)，那么这个\(x、y、z\)就是包含\(x\)以及比\(x\)小的数的可能性中最大的一种组合。
证明： 为什么不存在一个次小的\(y\)使得组合更大？ 首先我们知道，如果枚举了\(x\)，以及确定了\(y\)，那么\(z\)必然是确定的。 那么我们假设我们不选最大的\(Y\)，选一个次大的\(y\)，那么\(z\)必定是\(Y\)的因数，如果不是的\(Y\)的因数，那么取\(Y\)和\(z\)必然使得答案更优。 同理，也容易发现\(y\)也必定是\(Y\)的因数。 那么在\(y\)与\(z\)都是\(Y\)的因数的情况下，并且\(y \neq Y, z \neq Y\)，那么必然有\(y + z \leq Y\)。 所以肯定是选择最大的那个\(Y\)使得答案最优。
代码：
#include <bits/stdc++.h> using namespace std; #define N 200010 int n, a[N]; vector < vector <int> > vec; int main() { vec.clear(); vec.resize(200005); for (int i = 1; i <= 200000; ++i) { for (int j = i + i; j <= 200000; j += i) { vec[j].push_back(i); } } int T; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } sort(a + 1, a + 1 + n); n = unique(a + 1, a + 1 + n) - a - 1; int res = 0; map <int, int> mp; set <int, greater <int> > s; for (int i = 1; i <= n; ++i) { res = max(res, a[i]); for (auto it : vec[a[i]]) s.erase(it); mp[a[i]] = 1; if (!s.empty()) { int x = *s.begin(); res = max(res, a[i] + x); s.erase(x); for (auto it : vec[x]) s.erase(it); if (!s.empty()) { res = max(res, a[i] + x + *s.begin()); } for (auto it : vec[x]) if (mp.find(it) != mp.end()) s.insert(it); s.insert(x); } for (auto it : vec[a[i]]) if (mp.find(it) != mp.end()) s.insert(it); s.insert(a[i]); } printf("%d\n", res); } return 0; }转载于:https://www.cnblogs.com/Dup4/p/11095924.html
相关资源：JAVA上百实例源码以及开源项目