CodeForces 623B Array GCD

Posted on By 二价氢

题目大意

给定一个数列,进行下面两个操作之一:

  1. 花费删除一个连续子序列
  2. 每次花费,将一个数字加上或减去1,一个数只多被修改一次

询问使得整个数列的GCD大于1的最小花费

做法

简化问题,如果整个数列的GCD大于1,那么其一定是某个质数的倍数,由于我们肯定会保留下至少一个数,因而这个质数一定是之一的因子。

现在问题就是,给定质数,问如何通过最小花费,使得整个数列都是的倍数,因为操作1至多被执行一遍(执行多遍也一样),所以可以考虑用DP的方式完成,用,表示当前进行到第个数,flag表示删除数列的状态(删除之前,删除之间,删除之后),这里的转移方程非常好想,就不再赘述了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 5;
int arr[maxn], n, a, b;
bool np[maxn];
vector<int> pr, spr;
long long dp[maxn][3];
int main() {
	ios::sync_with_stdio(0);
	for (int i = 2; i < maxn; i++)
		if (!np[i]) {
			pr.push_back(i);
			for (int j = i + i; j < maxn; j += i)
				np[j] = true;
		}
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	int a1 = arr[1] - 1, a2 = arr[1], a3 = arr[1] + 1;
	int a4 = arr[n] - 1, a5 = arr[n], a6 = arr[n] + 1;
	for (int r : pr) {
		if (a1 % r == 0 || a2 % r == 0 || a3 % r == 0 ||
			a4 % r == 0 || a5 % r == 0 || a6 % r == 0) {
			spr.push_back(r);
			while (a1 % r == 0) a1 /= r;
			while (a2 % r == 0) a2 /= r;
			while (a3 % r == 0) a3 /= r;
			while (a4 % r == 0) a4 /= r;
			while (a5 % r == 0) a5 /= r;
			while (a6 % r == 0) a6 /= r;
		}
	}
	if (a1 != 1) spr.push_back(a1);
	if (a2 != 1) spr.push_back(a2);
	if (a3 != 1) spr.push_back(a3);
	if (a4 != 1) spr.push_back(a4);
	if (a5 != 1) spr.push_back(a5);
	if (a6 != 1) spr.push_back(a6);
	long long ans = 0x3f3f3f3f3f3f3f3fll;
	for (int p : spr) {
		memset(dp, 0x3f, sizeof(dp));
		dp[0][0] = 0;
		//cerr << "Prime = " << p << endl;
		for (int i = 1; i <= n; i++) {
			for (int j = -1; j <= 1; j++) {
				if (arr[i] + j != 1 && (arr[i] + j) % p == 0) {
					dp[i][0] = min(dp[i][0], dp[i - 1][0] + (j != 0) * b);
					dp[i][2] = min(dp[i][2], dp[i - 1][2] + (j != 0) * b);
				}
			}
			dp[i][1] = min(dp[i][1], dp[i - 1][0] + a); // Start
			dp[i][1] = min(dp[i][1], dp[i - 1][1] + a); // Continue
			dp[i][2] = min(dp[i][2], dp[i][1]); // End
			//cerr << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << endl;
		}
		ans = min(ans, min(dp[n][0], dp[n][2]));
	}
	cout << ans << endl;
	return 0;
}