• 欢迎光临~

Codeforces 891 A. Pride 做题记录(DP)

开发技术 开发技术 2022-12-30 次浏览

  原题链接:https://codeforces.com/problemset/problem/891/A

  一个比较显然的性质是如果序列的总$gcd$不为$1$,那么肯定是不存在解的。因为不管怎么样,都有一个因子无法消掉。

  单操作能让最多一个数变成$1$。很容易想到最好的情况就是每次操作都有一个数变成$1$。而在序列中存在$1$的情况下,每次操作都有一个数变成$1$是可以实现的($1$不断使旁边的数也变成$1$)。因此在序列中存在$cnt$个$1$的情况下,答案就是$n-cnt$。

  如果序列中没有$1$呢?只要序列的总$gcd$为$1$,我们就可以创造出$1$。对于创造$1$有几种情况:

  1)  序列中已经存在至少一对相邻数,它们的$gcd$是$1$。我们这样就只需要$1$次操作就能让序列中出现$1$。

  2)  序列中每一对相邻数,它们的$gcd$都不是$1$(但是序列的总$gcd$是$1$)。例如序列:$2$,$6$,$15$,$35$。这时我们不能$1$次操作就让序列中出现$1$。可以考虑枚举寻找序列中最少操作就能变成$1$的数,这个复杂度会达到$O(n^2)$,但是我们看数据规模才$2000$,复杂度可以接受。

  最终代码:

 

#include <cstdio>
using namespace std;
const int maxn=2000;
const int inf=0x3fffffff;

int n;
int a[maxn+5];

inline int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int g=a[1],cnt=0;
    bool flag=0;
    for (int i=1;i<=n;i++){
        if (g!=1)
            g=gcd(g,a[i]);
        if (a[i]==1)
            cnt++;
        if (gcd(a[i],a[i-1])==1)
            flag=1;
    }
    if (g!=1)
        puts("-1");
    else if (cnt||flag)
        printf("%d",n-cnt);
    else{
        int ans=inf;
        for (int i=1;i<=n;i++){
            g=a[i];
            for (int j=i+1;j<=n;j++){
                g=gcd(g,a[j]);
                if (g==1){
                    ans=(ans>j-i)?(j-i):ans;
                    break;
                }
            }
        }
        printf("%d",ans+n-1);
    }
    return 0;
} 

 

程序员灯塔
转载请注明原文链接:Codeforces 891 A. Pride 做题记录(DP)
喜欢 (0)