[LOJ6433]最大前缀和

深刻感受到自己的水平和机房里的其他人相差甚远，他们都是随手秒这个题的...

$n$很小，考虑状压DP

当一个序列在某个位置取到最大前缀和后，意味着如果把后面的数抽出来单独成序列，那么它的每个前缀和都$\leq0$，要不然就可以取到更大的前缀和了

令$s_i$表示状态为$i$的数的和，$f_i$表示选状态为$i$的数且最大前缀和$=s_i$的方案数，$g_i$表示选状态为$i$的数且每个前缀和都$\leq0$的方案数，那么答案就是$\sum\limits_is_if_ig_{mx-i}$

如果$s_i\gt0$，那么我们在$i$这个状态代表的序列前面加任何一个数，新的序列的最大前缀和肯定是总和，所以我们有转移$f_{j\cup i}\gets f_i(i\cap j=\varnothing)$

如果$s_i\leq0$，那么我们在$i$这个状态代表的序列末尾删除一个数得到的序列仍然满足条件，所以我们有转移$g_i\gets g_{i-j}(i\cap j\ne\varnothing)$

总时间复杂度$O(n2^n)$

#include<stdio.h>
const int maxn=1048576,mod=998244353;
typedef long long ll;
int a[20],s[maxn],f[maxn],g[maxn];
void inc(int&a,int b){(a+=b)%=mod;}
int main(){
	int n,i,j,mx,ans;
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",a+i);
	mx=1<<n;
	for(i=0;i<mx;i++){
		for(j=0;j<n;j++){
			if(i>>j&1)s[i]+=a[j];
		}
	}
	g[0]=1;
	for(i=0;i<mx;i++){
		if(s[i]<=0){
			for(j=0;j<n;j++){
				if(i>>j&1)inc(g[i],g[i^(1<<j)]);
			}
		}
	}
	for(i=0;i<n;i++)f[1<<i]=1;
	for(i=0;i<mx;i++){
		if(s[i]>0){
			for(j=0;j<n;j++){
				if(~i>>j&1)inc(f[i^(1<<j)],f[i]);
			}
		}
	}
	ans=0;
	for(i=0;i<mx;i++)inc(ans,s[i]*(ll)f[i]%mod*(ll)g[(mx-1)^i]%mod);
	inc(ans,mod);
	printf("%d",ans);
}

巴特西

[LOJ6433]最大前缀和

最新文章

热门文章