LibreOJ 3313 「ZJOI2020」序列

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

设所有操作构成的集族为 I，我们要做的实际上是为每一个操作赋一个权值，代表其被执行的次数，即 min∑S∈IxS,s.t.∑S∋ixS≤ai(si)−∑S∋ixS≤−ai(ti)xS≥0

做对偶，有 maxn∑i=1ai(si−ti),s.t.∑i∈S(si−ti)≤1(xS)si,ti≥0

我们令 bi=si−ti，那么限制就变成了比较优美的形式。
考虑直接进行 DP，设状态 fi,x,y,z 表示考虑到 i，以 i 为右端点的三类操作的 bi 之和的最大值分别为 x,y,z 时，∑ij=1ajbj 的最大值。
看起来状态数是爆炸的？

首先，注意到在这个问题中，虽然约束并非全幺模矩阵，但是容易发现最优解应当为整数（如果不为整数显然存在某种调整为整数的不劣解，感性上感觉可以归纳证明）。
最优解为整数，则状态可以仅保留 x,y,z∈{0,1}，也即每个时刻对 0 取 max，易知这样并不会丢失合法解。
既然状态只需要保留 {0,1}，那么 bi 的取值也只需要考虑 {−1,0,1}。这同样是显然的。

时间复杂度 O(∑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);
    }
}