P6631 [ZJOI2020] 序列

给你一个长为 $n$ 的非负整数序列 $a$，你可以进行区间减 $1$，区间奇数下标减 $1$，区间偶数下标减 $1$，请求出讲所有数变为 $0$ 的最小操作次数。

$1 \le n \le 10^5$。

记 $m$ 为操作种类数，$S_i$ 为第 $i$ 种操作涉及的下标集合，$x_i$ 为第 $i$ 种操作的操作次数，那么可以写成

$$\begin{aligned} \min \quad &\sum_{j=1}^{m} x_j \\ \texttt{s.t.} \quad &\sum_{j=1}^{m} [i \in S_j]x_j = a_i \quad i=1,2,...,n \\ &x_j \ge 0 \quad j=1,2,...,m \end{aligned}$$

对每个限制设一个乘数 $p_i$，加入最小化的式子中得到

$$\begin{aligned} &\sum_{j=1}^{m} x_j + \sum_{i=1}^{n} p_i (\sum_{j=1}^{m} [i \in S_j]x_i - a_i) \\ &=\sum_{j=1}^{m} (\sum_{i \in S_j} p_i + 1) x_j - \sum_{i=1}^{n} p_ia_i \end{aligned}$$

拉格朗日对偶，并将 $p_i$ 取反，得到

$$\begin{aligned} \max \quad &\sum_{i=1}^{n} p_ia_i \\ \texttt{s.t.} \quad &\sum_{i \in S_j} p_i \le 1 \quad j=1,2,...,m \\ \end{aligned}$$

描述一下就是求出一个序列 $p$ 使得每个可以一起操作的下标集合 $p$ 之和都 $\le 1$，求 $\sum_{i=1}^{n} a_ip_i$ 的最大值。

猜测有整数最优解。假设一个合法的 $p$ 有 $\le -2$ 的数，那么将其改为 $-1$ 仍然合法并且不劣。限制 $p$ 只能取 $-1,0,1$ 即可。

考虑 DP，记 $f_{i,0/1,0/1,0/1}$ 为枚举到 $i$，是否有和为 $1$ 的后缀，是否有后缀满足下标为偶数的和为 $1$，奇数，的最大值。转移枚举当前位选择 $-1,0,1$ 即可。时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+100,INF=1e18;
inline int in(int S,int i){ return (S>>i)&1; }
inline int chkmax(int &x,int y){ return y>x?x=y,1:0; }
#define gc getchar()
#define rd read()
inline int read(){
    int x=0,f=0; char c=gc;
    for(;c<'0'||c>'9';c=gc) f|=(c=='-');
    for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
    return f?-x:x;
}

int n,a[N],f[N][8];

void solve(){
    n=rd; for(int i=1;i<=n;++i) a[i]=rd;
    for(int i=0;i<=n;++i) for(int j=0;j<8;++j) f[i][j]=-INF; f[0][0]=0;
    for(int i=1;i<=n;++i){
        for(int j=0;j<8;++j){
            for(int x:{-1,0,1}){
                if(in(j,0)==1&&x==1) continue;
                if(i&1){ if(x!=1||!in(j,2)) chkmax(f[i][(in(j,0)+x==1)|(in(j,1)<<1)|((in(j,2)+x==1)<<2)],f[i-1][j]+x*a[i]); }
                else{ if(x!=1||!in(j,1)) chkmax(f[i][(in(j,0)+x==1)|((in(j,1)+x==1)<<1)|(in(j,2)<<2)],f[i-1][j]+x*a[i]); }
            }
        }
    }
    int ans=0; for(int i=0;i<8;++i) chkmax(ans,f[n][i]);
    printf("%lld\n", ans);
}

signed main(){

    int T=rd;
    while(T--) solve();

    return 0;
}