Codeforces 623B Array GCD

Array GCD

最后的序列里肯定有a[1], a[1]-1, a[1]+1, a[n], a[n]-1, a[n]+1中的一个，枚举质因子， dp去check

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std;

const int N = 1e6 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;

LL n, a, b, tot, ans = INF;
LL c[N], fac[100], dp[N][3];

void solve(int x) {
    for(int i = 2; i * i < x; i++) {
        if(x % i) continue;
        fac[tot++] = i;
        while(x % i == 0) x /= i;
    }
    if(x > 1) fac[tot++] = x;
    sort(fac, fac + tot);
    tot = unique(fac, fac + tot) - fac;
}

void calc(int fac) {
    memset(dp, INF, sizeof(dp));
    dp[0][0] = 0;
    for(int i = 0, r1, r2, r3; i < n; i++) {
        r1 = (c[i + 1] - 1) % fac;
        r2 = r1 + 1; if(r2 >= fac) r2 -= fac;
        r3 = r2 + 1; if(r3 >= fac) r3 -= fac;
        if(dp[i][0] < INF) {
            dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + a);
            if(!r2) dp[i + 1][0] = min(dp[i + 1][0], dp[i][0]);
            else if(!r1 || !r3) dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + b);
        }
        if(dp[i][1] < INF) {
            dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + a);
            if(!r2) dp[i + 1][2] = min(dp[i + 1][2], dp[i][1]);
            else if(!r1 || !r3) dp[i + 1][2] = min(dp[i + 1][2], dp[i][1] + b);
        }
        if(dp[i][2] < INF) {
            if(!r2) dp[i + 1][2] = min(dp[i + 1][2], dp[i][2]);
            else if(!r1 || !r3) dp[i + 1][2] = min(dp[i + 1][2], dp[i][2] + b);
        }
    }
    for(int i = 0; i < 3; i++)
        ans = min(ans, dp[n][i]);
}

int main() {
    scanf("%lld%lld%lld", &n, &a, &b);
    for(int i = 1; i <= n; i++) scanf("%lld", &c[i]);
    for(int i = -1; i <= 1; i++) solve(c[1] + i);
    for(int i = -1; i <= 1; i++) solve(c[n] + i);
    for(int i = 0; i < tot; i++) calc(fac[i]);
    printf("%lld
", ans);
    return 0;
}

/*
*/