Codeforces 891 A. Pride 做题记录（DP）

　　原题链接：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;
}