自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 23:12:35，当前版本为作者最后更新于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$。有以下转移：

• $f_{i,j}\gets f_{i-1,j-1}+x_i(0\le j-1<j\le n)$；
• $f_{i,j}\gets f_{i-1,j+1}-x_i(0\le j<j+1\le n)$。

上面的暴力 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;
}