LibreOJ 3313 「ZJOI2020」序列

感觉这个比 dxm 论文的做法简单很多啊（
orz EI，orz uyom！

设所有操作构成的集族为 I，我们要做的实际上是为每一个操作赋一个权值，代表其被执行的次数，即 min

做对偶，有 \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)，常数不用管（

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
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);
    }
}