LOJ #6433. 「PKUSC2018」最大前缀和

传送魔法：[biu~~~~~~~](https://loj.ac/problem/6433)

算是一道较有趣的$dp$了。

首先有一个简单的做法，状压$3$进制。
第$i$位是$0$表示$a_i$没有被考虑，
是$1$表示$a_i$在当前数列但是不在最大前缀和。
是$2$表示$a_i$在当前数列并且在最大前缀和中。
这样已经可以拿$50pts$了。

这个算法已经没有优化空间了。
我们从答案来考虑，
可以枚举最靠前的最大前缀和是哪些数，
发现一段要成为最大前缀和首先必须满足：
把后面一段拿出来单独看，每个前缀和都$\le 0$
那么我们可以对后面这段$dp$，每一次往后加一个数看前缀和合不合法就行了。
其次需要满足，当前的前缀和是最大的那一个。
这里我就不会了，去偷看了一下题解。

发现可以倒着$dp$，考虑倒着加入数，只要满足加入数之前的前缀和$> 0$即可

```
#include<cstdio>
#include<vector>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int mod = 998244353;
const int N = 20;
int f[1 << N], g[1 << N], sum[1 << N], a[N + 5], now, n;
int ans, tmp;
vector<int > bit[N + 5];

void Add(int &x, const int &a) {
	x += a; if(x >= mod) x -= mod;
}

int main() {
	scanf("%d", &n);
	int stmax = (1 << n) - 1;
	for(register int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	for(register int i = 0; i < 1 << n; ++i)
		bit[__builtin_popcount(i)].push_back(i);
	for(register int i = 1; i < 1 << n; ++i)
		sum[i] = sum[i - lowbit(i)] + a[__builtin_ctz(i)];
	f[0] = 1, g[0] = 1;
	for(register int i = 0; i < n; ++i) {
		for(register int j = bit[i].size() - 1; j >= 0; --j) {
			now = bit[i][j];
			if(sum[now] >= 0)
				for(register int k = 1, p = 0; p < n; k <<= 1, ++p) {
					if(now & k) continue;
					Add(f[now | k], f[now]);
				}
			for(register int k = 1, p = 0; p < n; k <<= 1, ++p) {
				if(now & k) continue;
				if(sum[now | k] >= 0) continue;
				Add(g[now | k], g[now]);
			}
		}
	}
	for(register int i = 1; i < 1 << n; ++i)
		Add(ans, ((1ll * sum[i] * g[stmax - i] % mod) * f[i] % mod + mod) % mod);
	printf("%d", (ans + mod) % mod);
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链