本文主要是介绍「PKUSC2018」最大前缀和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意
小 C 是一个算法竞赛爱好者,有一天小 C 遇到了一个非常难的问题:求一个序列的最大子段和。
但是小 C 并不会做这个题,于是小 C 决定把序列随机打乱,然后取序列的最大前缀和作为答案。
小 C 是一个非常有自知之明的人,他知道自己的算法完全不对,所以并不关心正确率,他只关心求出的解的期望值,现在请你帮他解决这个问题,由于答案可能非常复杂,所以你只需要输出答案乘上 n ! n! n! 后对 998244353 998244353 998244353 取模的值,显然这是个整数。
注:最大前缀和的定义: ∀ i ∈ [ 1 , n ] \forall i \in [1,n] ∀i∈[1,n], ∑ j = 1 i a j \sum_{j=1}^{i}a_j ∑j=1iaj的最大值。
数据范围
对于 10 % 10\% 10%的数据,有 1 ≤ n ≤ 9 1\leq n\leq 9 1≤n≤9。
对于 40 % 40\% 40%的数据,有 1 ≤ n ≤ 15 1\leq n\leq 15 1≤n≤15。
另有 10 % 10\% 10%的数据,满足 a a a中最多只有一个负数。
另有 10 % 10\% 10%的数据,满足 ∣ a [ i ] ∣ ≤ 2 |a[i]|\leq 2 ∣a[i]∣≤2。
对于 100 % 100\% 100%的数据,满足 1 ≤ n ≤ 20 1\leq n\leq 20 1≤n≤20, ∑ i = 1 n ∣ a [ i ] ∣ ≤ 1 0 9 \sum_{i=1}^{n}|a[i]|\leq 10^9 ∑i=1n∣a[i]∣≤109。
题解
发现如果直接无脑DP,怎么都要 O ( 3 N ) O(3^N) O(3N)
所以考虑本题有什么性质,考虑对于一个序列,它由它的最大前缀和的那段(设为A)以及后面的那段(设为B)组成,既然是最大前缀和,那么无论往后拓或往前缩都不会更优,转化为数学语言即为:A的任意后缀和都 ≥ 0 \ge0 ≥0(依题意不包括整段A的和),B的任意前缀和都 ≤ 0 \le0 ≤0,发现只需关心A和B的元素(不用关心顺序),所以根据性质,分别DP记录每种元素是否在里面,最后枚举A的元素组成,乘上对应方案数即可。
这篇关于「PKUSC2018」最大前缀和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!