CF623B Array GCD

朱雀 2021-11-29 12:18 259阅读 0赞

[CF623B Array GCD][]

> 给定一个序列 \\(a\_i\\) ，可以进行一下两种操作：
> 
>  *  删除一段长度为 \\(m\\) 的区间 \\((m<n)\\) ，花费为 \\(m\\times A\\) ，只能操作一次
>  *  可以花费 \\(b\\) 让一个元素 \\(+1\\) 或 \\(-1\\) ，每个元素只能操作一次
> 
> 求使得剩下的数最大公约数大于 \\(1\\) 的最小花费
> 
> \\(n\\leq10^6,\\ a\_\{i\}\\in\[2,\\ 10^9\]\\)

贪心，动态规划

--------------------

由于删除的区间长度小于 \\(n\\) ，则最优解剩下的序列一定包含 \\(a\_1\\) 和 \\(a\_n\\) ，则最后的 \\(\\gcd\\) 一定是 \\(a\_1,\\ a\_1+1,\\ a\_1-1, \\ a\_n,\\ a\_n+1,\\ a\_n-1\\) 其中之一的约数

由于每个数的不同质因子个数是 \\(\\log\\) 级别的，可以考虑枚举这 \\(6\\) 个数各自的质因子当作最大公约数

当确定了 \\(\\gcd\\) ，考虑如何求出最小花费

可以设计一个 dp，令 \\(f\_\{i,\\ 0/1/2\}\\) 为截至第 \\(i\\) 位，没有删除过区间 / 正在删除一段区间 / 已经删除了一段区间 所能得到的最小花费

可以列出方程 \\(\\begin\{cases\}f\_\{i,\\ 0\}=f\_\{i-1,\\ 0\}+cost\_i\\\\f\_\{i,\\ 1\}=\\min(f\_\{i-1,\\ 0\},\\ f\_\{i-1,\\ 1\})+A\\\\f\_\{i,\\ 2\}=\\min(f\_\{i-1,\\ 1\},\\ f\_\{i-1,\\ 2\})+cost\_i\\end\{cases\}\\)

时间复杂度 \\(O(n\\log n)\\)

代码

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6 + 10; ll f[3][maxn]; int n, A, B, a[maxn]; inline ll calc(int x, int P) { if (x % P == 0) return 0; if ((x + 1) % P == 0 || (x - 1) % P == 0) { return B; } return 1ll << 40; } inline ll check(int P) { bool flg = 1; f[1][0] = f[2][0] = 1ll << 40; for (int i = 1; i <= n; i++) { ll v = calc(a[i], P); f[0][i] = f[0][i - 1] + v; f[1][i] = min(f[0][i - 1], f[1][i - 1]) + A; f[2][i] = min(f[1][i - 1], f[2][i - 1]) + v; flg &= i == 1 || f[0][i - 1] > f[1][i - 1]; } return min(f[0][n], min(flg ? 1ll << 60: f[1][n], f[2][n])); } inline ll factor(int x) { int tmp = sqrt(x); ll res = 1ll << 60; for (int i = 2; i <= tmp; i++) { if (x % i == 0) { res = min(res, check(i)); while (x % i == 0) x /= i; } } if (x > 1) res = min(res, check(x)); return res; } int main() { scanf("%d %d %d", &n, &A, &B); for (int i = 1; i <= n; i++) { scanf("%d", a + i); } if (n == 1) return puts("0"); int s[7]; s[1] = a[1]; s[2] = a[1] - 1; s[3] = a[1] + 1; s[4] = a[n]; s[5] = a[n] - 1; s[6] = a[n] + 1; ll ans = 1ll << 60; for (int i = 1; i < 7; i++) { ans = min(ans, factor(s[i])); } printf("%I64d", ans); return 0; }

转载于:https://www.cnblogs.com/Juanzhang/p/11001692.html

[CF623B Array GCD]: http://codeforces.com/problemset/problem/623/B