正题

题目链接:https://www.luogu.com.cn/problem/P5369

题目大意

一个数列\(a\)的权值定义为\(max\{\sum_{i=1}^ka_i\}(k\in[1,n])\)

给出\(n\)个数字，求它们所有排列的权值和

\(1\leq n\leq 20\)

解题思路

设\(s_i,f_i,g_i\)分别表示集合\(i\)的权值和，集合\(i\)的所有排列中最大前缀和为\(s_i\)的方案数，集合\(i\)的所有排列中的最大前缀和为负的方案数。那么答案就是

\[\sum_{i=0}^{2^n-1} f_is_ig_{2^n-1-i}
\]

\(s_i\)很好求。\(g_i\)的话我们只转移\(s_i<0\)的就可以了，\(f_i\)的话我们考虑每次在前面插入一个数，那么只要原来的是最大前缀和，那么插入之后也一定是。

时间复杂度\(O(2^nn)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=21,P=998244353;

int n,a[N],lg[1<<N],s[1<<N],f[1<<N],g[1<<N],ans;

int main()

{

	scanf("%d",&n);

	for(int i=0;i<n;i++)scanf("%d",&a[i]);

	for(int i=0;i<n;i++)lg[1<<i]=i;

	int MS=(1<<n);f[0]=g[0]=1;

	for(int i=1;i<MS;i++){

		int p=i&-i;

		s[i]=(s[i-p]+a[lg[p]])%P;

	}

	for(int i=0;i<MS;i++){

		if(s[i]<0)continue;

		for(int j=0;j<n;j++){

			if(i&(1<<j))continue;

			(f[i|(1<<j)]+=f[i])%=P;

		}

	}

	for(int i=0;i<MS;i++){

		for(int j=0;j<n;j++){

			if(i&(1<<j))continue;

			int z=i|(1<<j);

			if(s[z]<0)(g[z]+=g[i])%=P;

		}

	}

	for(int i=0;i<MS;i++)

		(ans+=1ll*f[i]*g[MS-1-i]%P*s[i]%P)%=P;

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

	return 0;

}

巴特西

P5369-[PKUSC2018]最大前缀和【状压dp】

正题

题目大意

解题思路

code

最新文章

热门文章