点此看题面 https://www.luogu.com.cn/problem/P5369
大致题意: 对于一个序列, 求全排列下最大前缀和之和.
状压 \(DP\)
考虑如果单纯按照题目中对于最大前缀和的定义, 则一个序列它的最大前缀和是不唯一的.
为了方便统计, 我们姑且规定, 如果一个序列中存在多个最大前缀和, 我们取最靠后的一个.
由此我们想到, 对于一个序列可以把它分为两部分 \([1,k]\)和 \([k+1,n]\)满足:
\([1,k]\)是 \([1,k]\)本身的最大前缀和.
\([k+1,n]\)内所有前缀和均小于 \(0\).
显然, 由于 \([1,k]\)是其本身的最大前缀和, 而其之后每一段前缀和都小于 \(0\), 因此它就是整个序列的最大前缀和.
设 \([1,k]\)区间的点集为 \(i\),\(s_i\)为点集 \(i\)内数的和 (注意, 此处的和不取模, 要开 \(long\ long\) 存储),\(f_i\)为点集 \(i\)排列成的序列是其本身的最大前缀和的方案数,\(g_i\)为点集 \(i\)排列成的序列所有前缀和均小于 \(0\)的方案数 (易发现,\(f\) 和 \(g\)分别对应上面的两个条件).
则答案就是 \(\sum s_i\cdot f_i\cdot g_{2^{n-1}\ xor\ i}\)(结合前文自行理解).
\(DP\)转移
考虑 \(DP\)如何转移.
对于 \(f_i\), 我们可以枚举一个不在点集 \(i\)中的点 \(j\).
如果把 \(j\)放在点集 \(i\)排列成的序列的最后面, 显然不太好转移, 也无法利用 \(f\)本身的性质.
但如果我们把 \(j\)放在点集 \(i\)排列成的序列的最前面, 则只要 \(s_i\ge 0\), 显然有:
\(a_j\le a_j+s_i\).
对于除 \(a_j\)外的其他前缀 \(sum\), 由于在 \(f_i\)中满足 \(sum\le s_i\), 所以 \(a_j+sum\le a_j+s_i\)必然满足.
也就是说, 在 \(s_i\ge 0\)时, 可以保证此时点集排列成的序列是其本身的最大前缀和.
因此,\(f_{i|2^{j-1}}+=f_i\).
对于 \(g_i\), 我们同样枚举一个不在点集 \(i\)中的点 \(j\).
与之前不同, 这次我们可以直接把点 \(j\)放在点集 \(i\)排列成的序列的最后面.
因为在 \(g_i\)中满足所有前缀和均小于 \(0\), 此时在序列最后面新添了一个点, 并不会影响之前的前缀和.
而新添出的这个前缀和, 就是这个序列的和, 即 \(s_{i|2^{j-1}}\).
很显然, 若要满足条件, 当且仅当 \(s_{i|2^{j-1}}<0\).
也就是说, 在 \(s_{i|2^{j-1}}<0\)时, 可以保证此时点集排列成的序列所有前缀和均小于 \(0\).
因此,\(g_{i|2^{j-1}}+=g_i\).
代码
- #include<bits/stdc++.h>
- #define Tp template<typename Ty>
- #define Ts template<typename Ty,typename... Ar>
- #define Reg register
- #define RI Reg int
- #define Con const
- #define CI Con int&
- #define I inline
- #define W while
- #define N 20
- #define X 998244353
- #define Inc(x,y) ((x+=(y))>=X&&(x-=X))
- using namespace std;
- int n,a[N+5],f[1<<N],g[1<<N];long long s[1<<N];
- int main()
- {
- RI i,j,t,ans=0;for(scanf("%d",&n),i=1;i<=n;++i) scanf("%d",a+i);// 读入
- for(t=1<<n,i=0;i^t;++i) for(j=1;j<=n;++j) (i>>j-1)&1&&(s[i]+=a[j]);// 预处理 s[i]
- for(f[0]=1,i=0;i^t;++i) for(j=1;j<=n;++j) !((i>>j-1)&1)&&s[i]>=0&&Inc(f[i|(1<<j-1)],f[i]);//DP 转移 f[i]
- for(g[0]=1,i=0;i^t;++i) for(j=1;j<=n;++j) !((i>>j-1)&1)&&s[i|(1<<j-1)]<0&&Inc(g[i|(1<<j-1)],g[i]);//DP 转移 g[i]
- for(i=0;i^t;++i) ans=((s[i]%X+X)%X*f[i]%X*g[(t-1)^i]+ans)%X;return printf("%d",ans),0;// 统计答案
- }
[洛谷 5369] [PKUSC2018] 最大前缀和(状压 DP)
来源: http://www.bubuko.com/infodetail-3343740.html