CF2079B Arithmetic Exercise 题解

FFTotoro · 2025-04-07 15:30:13 · 题解

在阅读题解的过程中，你可能需要用到该云剪贴板中的部分代码辅助理解。

观察到每个元素 x 对最终答案的贡献必然是 x 或 -x，所以考虑给每个元素赋一个符号（+ 或 -，表示贡献系数为 1 或 -1）；考察怎样的贡献系数赋值方法可以对应一个操作序列：对于一个系数序列 k_1,k_2,\ldots,k_n(k_i\in\{1,-1\})，能对应一个操作序列当且仅当 \forall i,0\le\sum\limits_{j=1}^i k_j\le n。

据此可以设计一个 O(n^2) DP，f_{i,j} 表示考虑了前 i 个系数，系数和为 j 能得到的最大答案，初始值为 f_{0,0}=0。有以下转移：

上面的暴力 DP 实现可以参考云剪贴板中的 Code 1。

观察到这种“平移”的形式很像 slope trick 能做的东西，但是现在看起来还有一点麻烦。事实上，我们只需要对它做两个小修改即可：

• 令答案初始值为 -\sum\limits_{i=1}^m x_i，在第 i 轮 DP 时，对于上面第二个转移方程，将该轮的 DP 数组平移一位使其与上一轮的相同位置对齐，这样第一个转移方程变为 f_{i,j}\gets f_{i-1,j-2}+2x_i，第二个转移方程就可以忽略掉；（见云剪贴板中的 Code 2）
• 观察到事实上每一轮的 j-2\to j 可以改为 j-1\to j，因为在第奇数轮偶数的位置显然不会有值，反之亦然。当然这个时候数组下标的范围也需要进行一些修改。（见云剪贴板中的 Code 3）

于是该问题被转化成了一个经典的 slope trick 问题，可以使用 multiset 维护。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n,m; cin>>n>>m;
    vector<int> a(m);
    for(auto &i:a)cin>>i;
    reverse(a.begin(),a.end());
    long long w=-accumulate(a.begin(),a.end(),0ll);
    multiset<int,greater<> > s;
    for(int i=0,p=0;i<m;i++){
      int l=i+2>>1,r=i+n+1>>1;
      // 当前能够参与转移的下标的范围
      s.emplace(a[i]<<1);
      while(p<l)w+=*s.begin(),s.erase(s.begin()),p++;
      while(p+s.size()>r)s.erase(prev(s.end()));
    } // DP 过程
    for(int i:s)if(i>0)w+=i;
    cout<<w<<'\n';
  }
  return 0;
}