CF2244D

由于数组 b 的顺序和操作先后的顺序是没用的，并且我们改变符号时会影响到索引在前的改变符号的操作效果，所以对 b 进行升序排列。

假设我们从数组 b 中最终选择了 \(c_1,c_2,c_3,c_4(c_1 \lt c_2 \lt c_3 \lt c_4)\) 去操作，那么 \(a_1...a_{c_1}\) 进行了四次操作，符号不会改变，\(a_{c_1+1}...a_{c_2}\) 进行了三次操作，符号会改变，依次类推 \(a_{c_2+1}...a_{c_3}\) 符号不会改变，\(a_{c_3+1}...a_{c_4}\) 符号会改变。

推广到所有情况，可以发现最终所有操作的作用效果肯定是某一段数的符号被改变，而下一段数的符号不被改变，下下段数的符号又被改变，即改变符号的区间和不改变符号的区间相互交替。

于是我们便可以设计状态 \(dp_{i,0}\) 代表 \(a_i\) 的符号不被改变，即后面有偶数个操作。\(dp_{i,1}\) 代表 \(a_i\) 的符号被改变，即后面有奇数个操作。通过前缀和优化，我们可以只更新 i 为 b 中数的 \(dp_{i,0/1}\)。 $$ dp_{b_i,0}=\max_{j<i} {dp_{b_j,1}+S_{b_i}-S_{b_{j}}} $$

$$ dp_{b_i,1}=\max_{j<i} {dp_{b_j,0}+S_{b_{j}}}-S_{b_i} $$ 后面的前缀和体现出来了符号的改变和不改变，写代码的时候可以假设存在索引为 \(0\) 的操作（这样比较好写）。

这样看复杂度似乎过不去，但是我们发现 \(\max_{j<i} {dp_{b_j,1}+S_{b_i}-S_{b_{j}}}\) 和 \(\max_{j<i} {dp_{b_j,0}+S_{b_{j}}}-S_{b_i}\) 可以随着 \(i\) 的增大而更新，不用每次都遍历地算一遍。

对于一种操作序列的结尾处（假设为 \(b_m\)），它肯定只经历了一次操作，而后面的数未经历操作，即 \(dp_{b_m,1}+S_n-S_{b_m}\)。

再考虑上什么操作就不选的结果，答案就是 \(\max dp_{b_m,1}+S_n-S_{b_m}\) 和 \(S_n\) 的最大值。

代码就比较好写了。

#include<bits/stdc++.h>
#define int long long
#define INF 10000000000000000
using namespace std;
int T,n,m,a[214514],b[214514];
int suma[214514],dp[214514][2];
signed main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        int ans=-INF;
        for(int i=1;i<=n;i++) 
        {
            cin>>a[i];
            suma[i]=suma[i-1]+a[i];
        }
        for(int i=1;i<=m;i++) cin>>b[i];
        sort(b+1,b+1+m);
        dp[0][1]=0,dp[0][0]=0;
        int max1=0,max0=0;
        for(int i=1;i<=m;i++)
        {
            max0+=(suma[b[i]]-suma[b[i-1]]);
            max1+=(suma[b[i-1]]-suma[b[i]]);
            dp[b[i]][0]=max0;
            dp[b[i]][1]=max1;
            max0=max(max0,dp[b[i]][1]);
            max1=max(max1,dp[b[i]][0]);
            int nowsum=suma[n]-suma[b[i]];
            ans=max(ans,dp[b[i]][1]+nowsum);
        }
        cout<<max(suma[n],ans)<<endl;
    }
}

记录。