BUPT校内训练&Codeforces 623B 序列DP

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

Description

You are given array ai of length n. You may consecutively apply two operations to this array:
·remove some subsegment (continuous subsequence) of length m < n and pay for it m·a coins;
·change some elements of the array by at most 1, and pay b coins for each change.
Please note that each of operations may be applied at most once (and may be not applied at all) so you can remove only one segment and each number may be changed (increased or decreased) by at most 1. Also note, that you are not allowed to delete the whole array.
Your goal is to calculate the minimum number of coins that you need to spend in order to make the greatest common divisor of the elements of the resulting array be greater than 1.

Input

The first line of the input contains integers n, a and b (1 ≤ n ≤ 1 000 000, 0 ≤ a, b ≤ 109) — the length of the array, the cost of removing a single element in the first operation and the cost of changing an element, respectively.
The second line contains n integers ai (2 ≤ a_i ≤ 109) — elements of the array.

Output

Print a single number — the minimum cost of changes needed to obtain an array, such that the greatest common divisor of all its elements is greater than 1.

Example

Input

8 3 4
3 7 5 4 3 12 9 4

Output

13

题目大意

现在给你一个长度为n的序列,你要通过删除操作个修改操作使得整个序列的最大公约数大于1.
规则:
1.删除一个长度为m的子区间(不能是全部序列),花费m*a coins
2.对于序列中某一个元素加一或者减一,花费为b coins
现要求使得花费最小,且输出最小花费。


题解

这是一道序列DP,涉及修改和删除。
暴力gcd整个序列肯定是不可取的,我们来想想一个性质。
若要满足要求,则对于一个质数p,那么对于任意一个整数a,一定有(a±1)mod p ≠ a mod p;(这是显然的)。
既然有这样一个显而易见的性质,那么我们就可以省去讨论两个操作了,第二个操作可以不必去计入动态规划的状态,只需在枚举质数的时候,看看序列中的数要被这个质数整除是否需要+1或者-1就好。
于是我们设DP状态为

dp[i][j]

dp[i][0] 表示当前元素不在删除的序列中,且在处理第i个元素前,未删除过元素
dp[i][1] 表示当前元素包含于删除的序列中(第i个元素是删除序列的第一个元素或中间元素,即第i-1个元素可能在删除序列中,也可能不在删除序列中)
dp[i][2] 表示当前元素不在删除序列中,且删除的序列已经确定(即第i-1个元素可能是删除序列的最后一个,或不在删除序列中)

转移方程为:

dp[i][0] = dp[i-1][0] + cost;
dp[i][1] = min(dp[i-1][0],dp[i-1][1]) + a;
dp[i][2] = min(dp[i-1][1],dp[i-1][2]) + cost;

其中cost为对当前数进行非删除操作的费用,若无需改变则cost=0,否则cost=b


代码

#include 
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
typedef long long ll;
const int maxn = 1e6+5;
ll ans,dp[maxn][3];
int p[maxn],c[maxn];
int a,b,n,cnt;
bool ispr[maxn];
void get_prime(int x){
    for (int i = 2;i*i <= x;i++){
        if (x % i == 0)
            p[++cnt] = i;
        while (x % i == 0) x /= i;
    }
    if (x != 1) p[++cnt] = x;
    return;
}
void solve(int pr){
    memset(dp,0,sizeof(dp));
    for(int i = 1;i <= n;++i){
        ll cost = 1e12;
        if(c[i] % pr == 0)
            cost = 0;
        else if((c[i] - 1)%pr == 0 || (c[i] + 1) % pr == 0)
            cost = b;
        dp[i][0] = dp[i-1][0] + cost;
        dp[i][1] = min(dp[i-1][0],dp[i-1][1]) + a;
        dp[i][2] = min(dp[i-1][1],dp[i-1][2]) + cost;
    }
    for(int i = 0;i < 3;++i)
        ans = min(ans,dp[n][i]);
    return;
}
int main(){
    cnt = 0;
    n = get_num();
    a = get_num();
    b = get_num();
    for(int i = 1;i <= n;++i){
        c[i] = get_num();
    }
    for(int i = -1;i <= 1;++i){
        get_prime(c[1] + i);
        get_prime(c[n]+i);
    }
    sort(p+1,p+cnt+1);
    ans = 1e16;
    for(int i = 1;i <= cnt;++i){
        if(p[i] != p[i-1]){
            solve(p[i]);
        }
        else continue;
    }
    cout << ans << endl;
    return 0;
}​
Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00