感觉这个比 dxm 论文的做法简单很多啊（
orz EI，orz uyom！
设所有操作构成的集族为 \(\mathcal I\)，我们要做的实际上是为每一个操作赋一个权值，代表其被执行的次数，即 \[ \begin{array}{ccc} \min & \sum\limits_{S \in \mathcal I} x_S, & \\ \text{s.t.} & \sum\limits_{S \ni i} x_S \le a_i & (s_i) \\ & -\sum\limits_{S \ni i} x_S \le -a_i & (t_i) \\ & x_S \ge 0 & \end{array} \]
做对偶，有 \[ \begin{array}{ccc} \max & \sum\limits_{i=1}^n a_i (s_i - t_i), & \\ \text{s.t.} & \sum\limits_{i \in S} (s_i - t_i) \le 1 & (x_S) \\ & s_i,t_i \ge 0 & \end{array} \]
我们令 \(b_i = s_i-t_i\)，那么限制就变成了比较优美的形式。
考虑直接进行 DP，设状态 \(f_{i,x,y,z}\) 表示考虑到 \(i\)，以 \(i\) 为右端点的三类操作的 \(b_i\) 之和的最大值分别为 \(x,y,z\) 时，\(\sum_{j=1}^i a_j b_j\) 的最大值。
看起来状态数是爆炸的？
首先，注意到在这个问题中，虽然约束并非全幺模矩阵，但是容易发现最优解应当为整数（如果不为整数显然存在某种调整为整数的不劣解，感性上感觉可以归纳证明）。
最优解为整数，则状态可以仅保留 \(x,y,z \in \{0,1\}\)，也即每个时刻对 \(0\) 取 \(\max\)，易知这样并不会丢失合法解。
既然状态只需要保留 \(\{0,1\}\)，那么 \(b_i\) 的取值也只需要考虑 \(\{-1,0,1\}\)。这同样是显然的。
时间复杂度 \(O(\sum n)\)，常数不用管（
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using namespace std;
const int N = 1e5;
int T;
int n,a[N + 5];
long long f[N + 5][2][2][2],ans;
int main()
{
for(scanf("%d",&T);T;--T)
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
for(register int i = 2;i <= n;++i)
for(register int x = 0;x <= 1;++x)
for(register int y = 0;y <= 1;++y)
for(register int z = 0;z <= 1;++z)
f[i][x][y][z] = -0x3f3f3f3f3f3f3f3f;
ans = -0x3f3f3f3f3f3f3f3f;
f[1][0][0][0] = 0,f[1][1][1][0] = a[1];
for(register int i = 2;i <= n;++i)
for(register int j = -1;j <= 1;++j)
for(register int x = 0;x <= 1;++x)
for(register int y = 0;y <= 1;++y)
for(register int z = 0;z <= 1;++z)
if(x + j <= 1 && (i & 1 ? y : z) + j <= 1)
f[i][max(max(x + j,j),0)][i & 1 ? max(max(y + j,j),0) : y][i & 1 ? z : max(max(z + j,j),0)] = max(f[i][max(max(x + j,j),0)][i & 1 ? max(max(y + j,j),0) : y][i & 1 ? z : max(max(z + j,j),0)],f[i - 1][x][y][z] + j * a[i]);
for(register int x = 0;x <= 1;++x)
for(register int y = 0;y <= 1;++y)
for(register int z = 0;z <= 1;++z)
ans = max(ans,f[n][x][y][z]);
printf("%lld\n",ans);
}
}