题解 CF1421E 【Swedish Heroes】
青君
·
·
题解
Description
长度为 n 的数列 \big<a_i\big>，一次操作可以把两个相邻的数 a_i 与 a_{i+1} 合并成 -(a_i+a_{i+1})，请最大化 n-1 次操作后剩下的数。
1\le n\le 200000,-10^9\le a_i \le10^9
Solution
所有操作相当于给每个数前面分配一个 + 或 -，然后加起来。
很容易想到一个 \Theta(n^3) 的区间DP，设 f_{l,r} 表示合并 [l,r] 中的数后能得到的最大值，g_{l,r} 表示合并 [l,r] 中的数后能得到的最小值，有转移
f_{l,r}=\max_{l\le i < r}\{-(g_{l,i}+g_{i+1,r})\}
g_{l,r}=\min_{l\le i < r}\{-(f_{l,i}+f_{i+1,r})\}
然而这一点儿用都没有，没有任何优化余地。
凭经验可知我们一定少了什么observation ，是否所有合法的分配方案都满足一个简单的性质呢？
观察一下
$n=2$ `--`；
$n=3$ `++-`，`-++`；
$n=4$ `----`，`+---`，`-+--`，`--+-`,`---+`；
……
（我也不知道要多敏锐的洞察力才能）发现：
设 `-` 的个数为 $p$ ，`+` 的个数为 $q$，则
$$2p+q\equiv1\pmod{3}$$
证明用归纳法，假设 $n$ 成立，新合并一个数后，$p'=q+1$，$q'=p$，那么
$$2A=2*(2p'+q')\equiv4q+4+2p\pmod{3}$$
因为 $2p+q\equiv1\pmod{3}
2A\equiv3q+5\pmod{3}
2A\equiv2\pmod{3}
A\equiv1\pmod{3}
故 n+1 也成立。
但是别高兴得太早，这只是合法方案的必要条件，不是充分条件。事实上有这样一个corner case：类似+-+-... 或者 -+-+... 这样加减交错的情况一定是不合法的，因为第一次操作的两个数最后符号一定相同。
整理一下，合法的分配方案满足：
-
- 至少存在一对相邻且符号相同的数。
根据这两点设计一个DP:
设 f_{i,j,0/1,0/1} 表示考虑了前 i 个数，2p+q\equiv j\pmod{3}，第 i 个数的符号为 -或+，否/是存在至少一对相邻且符号相同的数，的答案。
转移枚举 a_i 的符号：
f_{i+1,(j+2)\bmod3,0,t|(k==0)}\gets f_{i,j,k,t}-a_{i+1}
f_{i+1,(j+1)\bmod3,1,t|(k==1)}\gets f_{i,j,k,t}+a_{i+1}
边界 f_{1,2,0,0}=-a_1,f_{1,1,1,0}=a_1。
## Comment
为我们提供了一种找规律的方向：**观察模性质**。
## Code
```cpp
#include<bits/stdc++.h>
#define mk make_pair
#define pk push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pi;
template<class T> bool cmax(T &x,T y){return y>x?x=y,1:0;}
template<class T> bool cmin(T &x,T y){return y<x?x=y,1:0;}
const int N=2e5+5;
int n,a[N];
LL f[N][3][2][2];
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
if(n==1){
cout<<a[1]<<endl;
return 0;
}
memset(f,-0x3f,sizeof f);
f[1][2][0][0]=-a[1];
f[1][1][1][0]=a[1];
for(int i=1;i<n;++i)
for(int j=0;j<3;++j)
for(int k=0;k<2;++k)
for(int t=0;t<2;++t)
cmax(f[i+1][(j+2)%3][0][t|(k==0)],f[i][j][k][t]-a[i+1]),
cmax(f[i+1][(j+1)%3][1][t|(k==1)],f[i][j][k][t]+a[i+1]);
cout<<max(f[n][1][0][1],f[n][1][1][1])<<endl;
return 0;
}
```