题解：P10299 [CCC 2024 S5] Chocolate Bar Partition

· · 题解

先把所有的数减去平均值。这样就要求每个连通块的和为 0。设 a 为减完之后的值，以及：

\begin{aligned} s_{i,j}&=\sum_{k=1}^{j} a_{i,k}\\ S_{j}&=s_{0,j}+s_{1,j} \end{aligned}

设计 DP。设 f(i) 为考虑前 i 列，且 (0,i) 和 (1,i) 相连时的连通块个数最大值。注意此时 (0,i) 所处的连通块内数之和一定为 S_i（因为前面的都组成完整连通块了，和必定为 0，故最靠后的那个连通块就是 S_i）。再设 g(i,j,k) 表示 (0,i) 和 (1,i) 不相连，且 (0,i) 所在连通块内目前数之和为 j、(1,i) 所在连通块内目前数之和为 k 时，连通块个数最大值。

转移如下：

\begin{aligned} f(i)&\gets \max\left(f(i-1),g(i-1,0,S_{i-1}),g(i-1,S_{i-1},0)\right)+[S_i=0]\\ g(i,j,k)&\gets g(i-1,j-a_{0,i},k-a_{1,i})+ [j=0]+[k=0]\\ g(i,S_{i-1}+a_{0,i},a_{1,i})&\gets f(i-1)+[S_{i-1}+a_{0,i}=0]+[a_{1,i}=0]\\ g(i,a_{0,i},S_{i-1}+a_{1,i})&\gets f(i-1)+[a_{0,i}=0]+[S_{i-1}+a_{1,i}=0] \end{aligned}

每个连通块会在结尾处统计。如果目前和为 0 就立刻结束这个连通块，并计入答案。

由于 g(i,j,k) 中永远有 j+k=S_i，故实际上只需要记 j。现在瓶颈在于上面的第二种转移。令 g(i,j,k)=g'(i,j-s_{0,i},k-s_{1,i})，存 g' 的值。这样第二类的就可以直接 g'(i)\gets g'(i-1) 继承过来了（但其中 [j=0] 和 [k=0] 还是要加的）。

时间复杂度 O(n)。需要使用 unordered_map 来存 g'。

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

template<class T,class U>
void cmax(T&x,const U&y){if(x<y)x=y;}

using ll=long long;

const int N=200005,inf=1e9;

int n,f[N];
ll sm,t[2][N],s[2][N],sum[N];
unordered_map<ll,int>mp;

int& g(int i,ll j){
    if(!mp.count(j-s[0][i]))mp[j-s[0][i]]=-inf;
    return mp[j-s[0][i]];
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(int i=0;i<2;i++)for(int j=1;j<=n;j++){
        cin>>t[i][j];
        sm+=t[i][j];
        t[i][j]*=n*2;
    }
    for(int i=0;i<2;i++)for(int j=1;j<=n;j++){
        t[i][j]-=sm;
        s[i][j]=s[i][j-1]+t[i][j];
    }
    for(int j=1;j<=n;j++)
        sum[j]=s[0][j]+s[1][j];
    f[0]=0;
    g(0,0)=0;
    for(int i=1;i<=n;i++){
        cmax(f[i],f[i-1]);//在一起->在一起
        cmax(f[i],g(i-1,0));//不在一起->在一起，上面被断开形成连通块
        cmax(f[i],g(i-1,sum[i-1]));//不在一起->在一起，下面被断开形成连通块
        if(sum[i]==0)f[i]++;//在这里断成一块

        //不在一起->不在一起的转移，每次使用偏移量维护
        g(i,0)++;//不在一起->不在一起，上面为0了，断成一块
        g(i,sum[i])++;//不在一起->不在一起，下面为0了，断成一块

        //在一起->不在一起，上面接续
        cmax(g(i,sum[i-1]+t[0][i]),f[i-1]+(sum[i-1]+t[0][i]==0)+(sum[i-1]+t[0][i]==sum[i]));
        //在一起->不在一起，下面接续，上面分开
        cmax(g(i,t[0][i]),f[i-1]+(t[0][i]==0)+(t[0][i]==sum[i]));
    }
    cout<<max(f[n],g(n,0))<<endl;
    return 0;
}