【鏈接】 我是鏈接,點我呀:)
【題意】

在這里輸入題意

【題解】

想一下,感覺最后的結果肯定是從某一段開始,這一段的gcd為1,然后向左和向右擴散的。
則枚舉那一段在哪個地方。
我們設這一段中所有的數字都做了一次gcd.

假設在i..j這一段。
則求gcd的順序是(i,i+1),(i+1,i+2)...(j-1,j)
這樣a[j]=gcd(a[i],a[i+1]..a[j])了

即順序求了一遍gcd.
這樣,預處理一下i到j的gcd.
如果gcd[i][j]==1,則獲取到一個可行方案。
求一下次數的最小值就好了
即(j-i)*2 + i-1 + n-j

當然,如果已經有1了,就沒必要去湊一個1出來了。
直接枚舉從1開始向左、向右就好。

【代碼】

#include <bits/stdc++.h> using namespace std;const int N = 2e3; int a[N+10],n; int f[N+10][N+10];int main(){#ifdef LOCAL_DEFINEfreopen("F:\\c++source\\rush_in.txt", "r", stdin);#endifscanf("%d",&n);for (int i = 1;i <= n;i++) scanf("%d",&a[i]);int ans = -1;//have 1for (int i = 1;i <= n;i++)if (a[i]==1){int cnt = 0;for (int j = i-1;j >= 1;j--)if (a[j]!=1){cnt++;}for (int j = i+1;j <= n;j++)if (a[j]!=1){cnt++;}if (ans==-1 || ans > cnt) ans = cnt;}int temp = a[1];for (int i = 2;i <=n;i++) {temp = __gcd(temp,a[i]); }if (temp!=1){puts("-1");return 0;}for (int i = 1;i <= n;i++){f[i][i] = a[i];for (int j = i+1;j <= n;j++){f[i][j] = __gcd(f[i][j-1],a[j]);}}for (int i = 1;i <= n;i++){for (int j = i;j <= n;j++)if (f[i][j]==1){int temp = (j-i)*2 + (i-1) + (n-j);if (ans==-1){ans = temp;}else ans = min(ans,temp);}}printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/AWCXV/p/7855800.html

總結

以上是生活随笔為你收集整理的【Codeforces Round #446 (Div. 2) C】Pride的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。