P8848 1 and -1 题解

· · 题解

我们分类讨论。

设 p 为 1 的个数，q 为 -1 的个数。

Part 1: p\le q

容易发现最小的最大子段和为 1，这也就意味着两个 1 之间一定有至少一个 -1（不然最大子段和大于 1 了）。

这样，就是在 q 个 -1 之间（包括两端）插入 p 个“隔板”1，方案总数为 C_{q+1}^{p}。

Part 2: p>q

在这种情况下，最大子段和为 p-q。我们画图分析。

![](https://cdn.luogu.com.cn/upload/image_hosting/42pxp08v.png) 就是如图从左下角到右上角的方案数。 设 $f{i,j}$ 为使用 $i$ 个 $-1$，前缀和为 $j$ 的方案数（使用 $i$ 个 $-1$ 就是如图从左上开始的层数，前缀和为 $j$ 就是当前高度），得到状态转移方程： $f_{i,j}=f_{i-1,j+1}+f_{i,j-1}

初始化 f_{0,0}=1。

答案为 f_{q,p-q}。

code:

注意空间复杂度，可以选择用 vector，也可以用滚动数组（这个更好）。

#include<bits/stdc++.h>
using namespace std;
const int N=10086;
const int mod=998244353;
typedef long long ll;
int n,cp=0,cq=0;
vector<int> a[N];
signed main(){
    int x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&x),x==1?cp++:cq++;
    int m=cp-cq;
    //a[0].push_back(1);
    if(m>0){
        for(int i=0;i<=cq;i++)
        for(int j=0;j<=m;j++){
            int s=0;
            if(i&&j!=m)s+=a[i-1][j+1];
            if(j)s+=a[i][j-1];
            a[i].push_back(i||j?s%mod:1);
            //printf("%d ",i||j?s%mod:1);
        }
        printf("%d",a[cq][m]);
    }
    else{
        for(int i=0;i<=1-m;i++)
        for(int j=0;j<=cp;j++){
            int s=0;
            if(i)s+=a[i-1][j];
            if(j)s+=a[i][j-1];
            a[i].push_back(i||j?s%mod:1);
        }
        printf("%d",a[1-m][cp]);
    }
    return 0;
}