P8940 题解（2023 激励计划评分 8）

FFTotoro · 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;
}