[CodeQUEEN2023 Final E] Good Partition 题解

FFTotoro · 2023-08-08 17:59:22 · 题解

关于比赛

比赛链接：CodeQUEEN2023 决赛。

日本的一个非官方女生竞赛。

两个有趣的事实：

• 虽然这是女生竞赛，但是规则上写着——只要心理性别是女就可以参加决赛（
• 上次莆田市 CSP-S 集训 Day 2，@RSY 出的题，结果 T2 有歧义，导致一堆人（包括我）读错题意该题爆零（白送一个 Rank 1）。结果我们读错的题意居然就是这个 E……

题目解法

参考了 \color{Orange}\mathrm{MMNMM} 的日语题解。

首先，我们可得任意一组 \sum S(B_i) 都能写为 \sum x_iA_i 的形式，其中 x_1,x_2,\ldots,x_N 满足以下条件：

考虑为什么要这么定义。显然对于一段 B_i 我们只会取它其中的两个数作为产生其极差的最大值和最小值（事实上其中一种最优的构造方案就是对于每个 B_i 取它的左右两端点作为极差，证明显然），因此第二点很好证明——A_i 的贡献形如 \cdots,0,-A_i,0,\cdots,0,A_j,0,\cdots（中间那个段极差就是 A_j-A_i）或者 \cdots,0,A_i,0,\cdots,0,-A_j,0,\cdots。至于第三点，显然每个 1 都能跟一个 -1 匹配，总和为 0。

观察到还有一个很重要的点，就是对于任意满足上面条件的 x，都可以构造 B 使得 \sum x_iA_i\le\sum S(B_i)。证明平凡，有需要可以参考官方题解。大体就是对于每一个 B_i 分开考虑即可。

这样显然 \max\{\sum x_iA_i\}=\max\{\sum S(B_i)\}。可以用反证法证明。

至于怎么求最大值，滚动数组优化 DP 即可。时间复杂度 O(N)，空间复杂度 O(1)。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int n,x=0,y=-1e18,z=y; cin>>n;
  while(n--){
    int a; cin>>a;
    int m=max({x,y+a,z-a});
    y=max(y,x-a),z=max(z,x+a),x=m;
  }
  cout<<x<<endl;
  return 0;
}