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 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-; LL n, a, b, tot, ans = INF;
LL c[N], fac[], dp[N][]; void solve(int x) {
for(int i = ; i * i < x; i++) {
if(x % i) continue;
fac[tot++] = i;
while(x % i == ) x /= i;
}
if(x > ) fac[tot++] = x;
sort(fac, fac + tot);
tot = unique(fac, fac + tot) - fac;
} void calc(int fac) {
memset(dp, INF, sizeof(dp));
dp[][] = ;
for(int i = , r1, r2, r3; i < n; i++) {
r1 = (c[i + ] - ) % fac;
r2 = r1 + ; if(r2 >= fac) r2 -= fac;
r3 = r2 + ; if(r3 >= fac) r3 -= fac;
if(dp[i][] < INF) {
dp[i + ][] = min(dp[i + ][], dp[i][] + a);
if(!r2) dp[i + ][] = min(dp[i + ][], dp[i][]);
else if(!r1 || !r3) dp[i + ][] = min(dp[i + ][], dp[i][] + b);
}
if(dp[i][] < INF) {
dp[i + ][] = min(dp[i + ][], dp[i][] + a);
if(!r2) dp[i + ][] = min(dp[i + ][], dp[i][]);
else if(!r1 || !r3) dp[i + ][] = min(dp[i + ][], dp[i][] + b);
}
if(dp[i][] < INF) {
if(!r2) dp[i + ][] = min(dp[i + ][], dp[i][]);
else if(!r1 || !r3) dp[i + ][] = min(dp[i + ][], dp[i][] + b);
}
}
for(int i = ; i < ; i++)
ans = min(ans, dp[n][i]);
} int main() {
scanf("%lld%lld%lld", &n, &a, &b);
for(int i = ; i <= n; i++) scanf("%lld", &c[i]);
for(int i = -; i <= ; i++) solve(c[] + i);
for(int i = -; i <= ; i++) solve(c[n] + i);
for(int i = ; i < tot; i++) calc(fac[i]);
printf("%lld\n", ans);
return ;
} /*
*/
上一篇:android事件分发机制


下一篇:51Nod 1305 Pairwise Sum and Divide | 思维 数学