题目大意
给定一个数列，进行下面两个操作之一：
- 花费\(a\cdot \mathrm{Len}(S)\)删除一个连续子序列\(S\)
- 每次花费\(b\)，将一个数字加上或减去1，一个数只多被修改一次
询问使得整个数列的GCD大于1的最小花费
做法
简化问题，如果整个数列的GCD大于1，那么其一定是某个质数\(p\)的倍数，由于我们肯定会保留下至少一个数，因而这个质数\(p\)一定是\(a_1 - 1, a_1, a_1 + 1, a_n - 1, a_n, a_n + 1\)之一的因子。
现在问题就是，给定质数\(p\)，问如何通过最小花费，使得整个数列都是\(p\)的倍数，因为操作1至多被执行一遍（执行多遍也一样），所以可以考虑用DP的方式完成，用\(f_{i,flag}\)，表示当前进行到第\(i\)个数，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;
}