LOJ 6433 「PKUSC2018」最大前缀和——状压DP

题目：https://loj.ac/problem/6433

想到一个方案中没有被选的后缀满足 “该后缀的任一前缀和 <=0 ”。

于是令 dp[ S ] 表示选了点集 S ，满足任一前缀和 <=0 的方案。很好转移。

令 f[ S ] 表示选了点集 S ，且 S 整体就是最大前缀和的方案。

只会 3 做出 f[ ] ，就是考虑容斥， \( f[s]=|s|! - \sum f[d]*dp[s^d] (sm[d]>=sm[s]) \) ，其中 sm[ s ] 表示点集 s 的权值和。

然后看了题解。发现 “ S 整体是最大前缀和 ” <==> “ S 的任一后缀和 >0 ” ，所以像做 dp[ ] 一样，从后往前放数字就能转移了！！！

还要训练思维。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int Mx(int a,int b){return a>b?a:b;}

const int N=,M=(<<)+,mod=;

int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}

int n,a[N],dp[M],f[M]; ll sm[M];

int ct[M],bin[N],lg[M],jc[N];

namespace S1{

  void solve(int cnt)

  {

    int ans=;for(int i=;i<=n;i++)ans=upt(ans+a[i]);

    for(int i=;i<=n;i++)ans=(ll)ans*i%mod;

    if(!cnt||n==){printf("%d\n",ans); return;}//n==1!!

    int rt,U=bin[n]-;

    for(int i=;i<=n;i++)if(a[i]<){rt=i-;break;}//i-1 for bin[]

    for(int s=;s<U;s++)//s<U

      if((s&bin[rt])&&sm[s]<)

    ans=upt(ans-(ll)jc[ct[U^s]]*jc[ct[s]-]%mod*sm[s]%mod);

    printf("%d\n",ans);

  }

}

namespace S2{

  int dp[M][],mn[M],mx[M],fx=;

  void init()

  {

    for(int s=;s<bin[n];s++)

      for(int i=;i<=n;i++)

    if(s&bin[i-])

      {if(a[i]>)mx[s]+=a[i];else mn[s]+=a[i];}

  }

  void solve()

  {

    init(); dp[][]=;int U=bin[n]-;

    mn[]=mx[]=-;///

    //0 not 0+fx for 'none' can't be cal

    for(int s=;s<U;s++)

      {

    int tp=U^s,d;

    while(tp)

      {

        d=tp&-tp; tp^=d; d|=s;

        for(int i=mn[s];i<=mx[s];i++)

          if(dp[s][i+fx])

        {

          int j=Mx(i,sm[d])+fx;

          dp[d][j]=upt(dp[d][j]+dp[s][i+fx]);

        }

      }

      }

    int ans=;

    for(int i=mn[U];i<=mx[U];i++)

      if(dp[U][i+fx])

    ans=(ans+(ll)dp[U][i+fx]*i)%mod;

    printf("%d\n",upt(ans));//upt

  }

}

void init()

{

  bin[]=; lg[]=;

  for(int i=;i<=n;i++)

    bin[i]=bin[i-]<<,lg[bin[i]]=i;

  jc[]=;for(int i=;i<=n;i++)jc[i]=(ll)jc[i-]*i%mod;

  for(int s=;s<bin[n];s++)

    {

      sm[s]=sm[s^(s&-s)]+a[lg[s&-s]+];

      ct[s]=ct[s^(s&-s)]+;

    }

}

int main()

{

  scanf("%d",&n); bool fg=;int cnt=;

  for(int i=;i<=n;i++)

    {

      scanf("%d",&a[i]);

      if(a[i]<-||a[i]>)fg=;

      if(a[i]<)cnt++;

    }

  init();

  if(cnt<=){S1::solve(cnt);return ;}

  if(!fg){S2::solve();return ;}

  dp[]=;

  for(int s=;s<bin[n];s++)

    {

      if(sm[s]>)continue;

      for(int i=;i<=n;i++)

    if(s&bin[i-])

      {

        int d=s^bin[i-];

        if(dp[d])dp[s]=upt(dp[s]+dp[d]);

      }

    }

  f[]=;

  for(int s=;s<bin[n];s++)

    for(int i=;i<=n;i++)

      if(s&bin[i-])

    {

      int d=s^bin[i-];

      if(sm[d]>||!d)f[s]=upt(f[s]+f[d]);//!d

    }

  int ans=;

  for(int s=,U=bin[n]-;s<bin[n];s++)

    if(f[s]&&dp[U^s])

      ans=(ans+sm[s]%mod*f[s]%mod*dp[U^s])%mod;

  printf("%d\n",upt(ans));

  return ;

}