题解 P5369 【[PKUSC2018]最大前缀和】

· · 题解

一丶前言

为了方便，定义/说明一些东西：

若存在多个p使得\sum_{i=1}^{p}{a_i}最大，默认最大的一个p是它的最大前缀和。

真后缀的含义即为除了整体以外的后缀 ## 二丶思路 题目大意很清楚了吧，就是求$n$个数所有排列的最大前缀和之和，答案对$998244353$取模。 既然要求最大前缀和，我们先看看最大前缀和有些什么性质，假设$\sum_{i=1}^{p}a_i$是最大前缀和，那么： 1. 不存在$x(1<x<=p)$，使得$\sum_{i=x}^{p}a_i<0$，即没有任何一段**真**后缀和$<0$（不然我们把这一段舍去答案就更大了） 2. 不存在$x(p<x<=n)$，使得$\sum_{i=p+1}^{x}a_i>=0$，即没有任何一段前缀和$>=0$（否则我们把这一段加上之后更优） 显然条件$1$只跟前$p$个数有关，条件2只跟后$n-p$个数有关，因此我们考虑分开$DP$： 假设$f[S]$是集合$S$为最大前缀和时，集合$S$的排列满足条件$1$的方案。 $g[U$^$S]$是集合$S$为最大前缀和时，集合$U-S$的排列满足条件$2$的方案数。 并假设$sum[S]=\sum_{i\in S}a_i

所以ans=\sum_{S\subset U}sum[S]*f[S]*g[U-S]，问题就在于如何求f和g了

我们假设f是从后面往前面加数，g是从前面往后面加数（注意理解这句话），那么g的DP方程就很简单了：

以此类推，$f$的$DP$方程貌似也很类似，就是： $f[S|u]+=f[S](sum[S|u]>=0)

但是这样只能拿到55分，为什么呢？因为我们说的是没有任何一段真后缀和 <0，而不是后缀，所以这样会漏掉一部分。

那我们稍稍改一改就行了，我的方法是假设一个f[S][0/1]：

$f[S][1]$则是$sum[S]>=0$的情况，且它的任何真后缀都$>=0$的方案数。 $DP$方程也稍稍改改就好了： $f[S|u][0]+=f[S][1](sum[S|u]<0) f[S|u][1]+=f[S][1](sum[S|u]>=0)

则ans=\sum_{S \subset U}(f[S][0]+f[S][1])* sum[S]*g[U^S]

三丶代码

#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define N 21
#define mod 998244353
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
    char ch=getchar();
    ll s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
inline ll Z(ll x){return x>=mod?x-mod:x;}
ll sum[1<<N];ll f[1<<N][2],g[1<<N];
ll n,a[N];
int main()
{
    n=read();
    for(register ll i=1;i<=n;i++)a[i]=read();
    for(register ll i=0;i<(1<<n);i++)
    {
        for(register ll j=1;j<=n;j++)
        {
            if(i&(1<<(j-1)))sum[i]=sum[i]+a[j];
        }
    }
    for(register ll i=1;i<=n;i++)if(a[i]<0)f[1<<(i-1)][0]=1;else f[1<<(i-1)][1]=1;//初始化
    for(register ll i=1;i<(1<<n);i++)
    {
        ll S=i;
        for(register ll j=1;j<=n;j++)
        {
            if(S&(1<<(j-1)))continue;
            ll T=S|(1<<(j-1));
            if(sum[T]>=0)f[T][1]=Z(f[T][1]+f[S][1]);
            else f[T][0]=Z(f[T][0]+f[S][1]);
        }
    }
    g[0]=1;
    for(register ll i=0;i<(1<<n);i++)
    {
        ll S=i;if(!g[S])continue;
        for(register ll j=1;j<=n;j++)
        {
            if(S&(1<<(j-1)))continue;
            ll T=S|(1<<(j-1));
            if(sum[T]<0)g[T]=Z(g[T]+g[S]);
        }
    }

    ll U=(1<<n)-1,ans=0;
    for(register ll i=1;i<=U;i++)
    {
        ans=Z(ans+Z(sum[i]%mod+mod)*Z(f[i][0]+f[i][1])%mod*g[U^i]%mod);
    }
    printf("%lld\n",ans);
    return 0;
}
/*
3
0 1 -2
*/

如果认为我这篇题解对你有帮助的可以给我点一下赞qwq。如果有任何疑问，或者认为我的题解有什么问题的话，请务必私信我，感激不尽！我会努力把我的题解写得最好的!