自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:43:57，当前版本为作者最后更新于2023-12-24 21:33:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

怎么跟昨晚 ABC334 的 F 有异曲同工之妙啊，但是昨晚 F 多了个转移的限制，可以用单调队列解决，本题则只需要记录一个最小值。做完这题可以使用 [ABC334F] Christmas Present 2 练练手。

解法

显然最后整个数组的元素都会变成原数组中所有元素的 $\gcd$，令其为 $g_0$。

于是考虑一些本来就不用变动的元素，它们将数组划分成了若干个段（即 $a_i\ne g_0$ 的元素构成的若干个段）。这些段可以使用 std::vector 存储 std::pair 实现。注意代码中存储的段是左闭右开的，即存储方式类似 $[l_i,r_i)$。

如果这样的段不存在，也就是说原数组所有元素都相等，答案为 $0$。

否则进行 DP。令 $f_i$ 表示处理到第 $i$ 个段 $[l_i,r_i)$ 时的最小代价，$g_i$ 表示 $a_{[l_i,r_i)}$ 间元素的 $\gcd$，那么 $f_i$ 可能有两种来源：

• 仅仅将段内进行操作，不操作两端值为 $g_0$ 的元素：$f_i\leftarrow f_{i-1}+r_i-l_i+k+[g_i\ne g_0]$（为什么要考虑 $g_i\ne g_0$？此时需要将它两边的其中一个 $g_0$ 一起操作，这样才能使这一段的值全部变为 $g_0$）；

• 和前面的段（这里是从第 $j$ 段开始）连在一起操作：$f_i\leftarrow\min\{f_{j-1}+r_i-l_j+k\}$，而后面的式子可以变为 $\min\{f_{j-1}-l_j\}+r_i+k$，所以只需用一个变量维护 $f_{j-1}-l_j$ 的最小值即可。

示例代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,k,g0=0,l=0,m=2e9; cin>>n>>k;
  vector<int> a(n);
  for(auto &i:a)cin>>i,g0=gcd(g0,i);
  vector<pii> b;
  while(1){
    while(l<n&&a[l]==g0)l++;
    if(l==n)break;
    int r=l+1;
    while(r<n&&a[r]!=g0)r++;
    b.emplace_back(l,r),l=r;
  } // 找段的过程
  if(b.empty())cout<<"0\n",exit(0);
  vector<int> f(b.size());
  for(int i=0;i<b.size();i++){
    auto [l,r]=b[i]; int g=0;
    for(int j=l;j<r;j++)g=gcd(g,a[j]);
    f[i]=(i?f[i-1]:0)+r-l+(g!=g0)+k;
    if(m<2e9)f[i]=min(f[i],r+m+k);
    m=min(m,(i?f[i-1]:0)-l);
  } // 按照上面的方程转移
  cout<<f[b.size()-1]<<endl; // 答案
  return 0;
}