[ARC085E] MUL 题解

swiftc · 2023-04-04 07:26:02 · 题解

设 solve(S) 为只考虑 S 这个集合内数时的答案，我们将每一个数向它的倍数连边建出一张无向图，容易发现如果这张图不连通每一个连通块是互不影响的（因为无论怎么选都不会导致另一个连通块内的点被删除），于是可以枚举最小的数选不选，如果删除之后不连通就分别调用 solve 解决，感性理解一下可以发现在较小的数都被决策完之后图上的连通块不可能十分大，这种做法在 n \le 100 时可以在较短的时间内通过。

#include <bits/stdc++.h>
#define N 110
#define ll long long
using namespace std;
int n, val[N], vis[N];
vector<int> v[N];
ll solve(vector<int> c) {
  if (c.empty())
    return 0;
  for (auto x : c)
    vis[x] = 1;
  queue<int> q;
  vis[c.front()] = 0, q.push(c.front());
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (auto to : v[x]) {
      if (vis[to]) {
        vis[to] = 0;
        q.push(to);
      }
    }
  }
  vector<int> a, b;
  for (auto x : c) {
    if (!vis[x]) {
      if (x != c.front())
        a.push_back(x);
    } else
      vis[x] = 0, b.push_back(x);
  }
  vector<int> tmp;
  for (auto x : a)
    if (x % c.front())
      tmp.push_back(x);
  return solve(b) + max(solve(tmp), solve(a) + val[c.front()]);
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i++)
    cin >> val[i];
  for (int i = 1; i <= n; i++)
    for (int j = 2; i * j <= n; j++)
      v[i].push_back(i * j), v[i * j].push_back(i);
  vector<int> c;
  for (int i = 1; i <= n; i++)
    c.push_back(i);
  cout << solve(c) << '\n';
  return 0;
}