Divan and Kostomuksha (easy version) dp，gcd（2100）

题意 ：

• 对于给定序列，任意打乱顺序，问 ：$$\sum _{i=1}^{n}gcd(a_1,a_2,...,a_n)$$的最大值是多少

思路 ：

• 序列的gcd一定是递减的
• 设$cnt(i)$表示以i为因数（包含i）的数字的数量，$dp[i]$表示将i放在第一个的答案
• 转移方程为$dp[j]=max(dp[j],dp[i]+cnt(j)\ast (j-i)+dp[i])$
• 这个方程的意义是，选择$cnt(j)$个数字放在最前面，那么产生的gcd贡献是$cnt(j)\ast j$
• 那么对于后一段填不了j倍数的位置，不能产生j的贡献
• 后一段的贡献怎么算呢？可以枚举j的因数（不包含j）（因为后面的数如果不是j的因数，同时也不是j的倍数，产生的贡献为1，这等价于填1，而1也是j的因数 <- 这是一个关键的思路，删繁就简）
• 对于j的因数i（i!=j），因为$dp[i]$算的是整个序列的答案，那么后一段也包含进去了，但是前一段会有重复计算，产生贡献为$i\ast cnt[j]$（gcd为i，一共$cnt(j)$个数字），要减去这个贡献

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <unordered_set> #include <math.h> #define endl '\n' #define fi first #define se second #define pb push_backusing namespace std; using ll = long long;typedef pair<int, int> PII;const int N = 5e6 + 10;ll cnt[N]; ll dp[N];int main() {cin.tie(nullptr) -> sync_with_stdio(false);int n; cin >> n;for (int i = 1, x; i <= n && cin >> x; i ++ ) ++ cnt[x];// cnt[i]表示i的倍数（包括i）的数量for (int i = 1; i < N; i ++ )for (int j = i + i; j < N; j += i)cnt[i] += cnt[j];dp[1] = n;ll ans = 0;for (int i = 1; i < N; i ++ ) // i是j的约数（不包含j）{for (int j = i + i; j < N; j += i)dp[j] = max(dp[j], dp[i] + (j - i) * cnt[j]);ans = max(ans, dp[i]); // 边转移边统计答案}cout << ans << endl;return 0; }

总结

以上是生活随笔为你收集整理的Divan and Kostomuksha (easy version) dp，gcd（2100）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。