题目描述

有 n 个小朋友排成一列。每个小朋友手上都有一个数字,这个数字可正可负。规定每个小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最少有一个)小朋友手上的数字之和的最大值。

作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的:第一个小朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人),小朋友分数加上其特征值的最大值。

请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对 p 取模后输出。

对于 100%的数据,1 ≤ n ≤ 1,000,000,1 ≤ p ≤ 10^9,其他数字的绝对值均不超过 10^9。

求的就是1.特征值 2.分数。

特征值:

算法一:【dp】P1982 小朋友的数字-LMLPHP

静态前缀和。

直接枚举出所有的情况(两前缀和之差就是一段区间的sum值),取max。顺便取一下【dp】P1982 小朋友的数字-LMLPHP因为当前这一位存在意义就是它被取为最大区间的值,否则就应当取之前的special值,以维持它的不下降性质。但是如果想把这种思路优化到【dp】P1982 小朋友的数字-LMLPHP的话,是不可以的。例如这组数据:“3 -2 3”,value[2]对于special[1]是没有意义的,但是value[1]+value[2]>0故对于special[3]有意义。

由此引申到算法二

算法二:

这是一个假算法:看做很多个子段和,还有分开的前缀和,但是不能保证每一个值是前面的最大值

算法三:【dp】P1982 小朋友的数字-LMLPHP

这不就是最大子段和的入门题吗(某年初赛题)然后再维持一下最大值以及顺序赋值就可以了

分数:

由题面可以得到【dp】P1982 小朋友的数字-LMLPHP【dp】P1982 小朋友的数字-LMLPHP。并且在【dp】P1982 小朋友的数字-LMLPHP中维持不下降的性质(当【dp】P1982 小朋友的数字-LMLPHP时,答案可能是【dp】P1982 小朋友的数字-LMLPHP;当【dp】P1982 小朋友的数字-LMLPHP,答案必为【dp】P1982 小朋友的数字-LMLPHP)。那么就容易得到【dp】P1982 小朋友的数字-LMLPHP。因为计算过程中有可能爆精度,但又不能马上模,一种是C++中__int128,另一种是当【dp】P1982 小朋友的数字-LMLPHP时就能确定【dp】P1982 小朋友的数字-LMLPHP(但是!但是!这个方法 虽然 被很多AC数据采用,但是遇到如:8 66 -511657297 151810723 -588294472 -271526366 58051666 -792123397 -76376854 -36217375 此数据时会计算出错误答案!)。如果坚持正解的话,还是用大整数或者__int128(C++)吧。

那么怎么计算【dp】P1982 小朋友的数字-LMLPHP呢?

题目的计算方法是【dp】P1982 小朋友的数字-LMLPHP

我们可以发现,【dp】P1982 小朋友的数字-LMLPHP

所以当计算【dp】P1982 小朋友的数字-LMLPHP时,我们只需要比较【dp】P1982 小朋友的数字-LMLPHP【dp】P1982 小朋友的数字-LMLPHP,即看【dp】P1982 小朋友的数字-LMLPHP的正负

同样的,我们需要维持这个序列的不下降性。于是就过了。

“将其绝对值对 p 取模后输出”我是先取绝对值,再按原符号not x + 1 (get到了转相反数的位运算)

另外,模数是个麻烦的问题。最早的时候,我是输入就模、计算就模,但是我忽略了一个非常明显的问题:最大值 模后 不一定最大,就是说这样计算出来的只是模后最大值。所以用以上的“另一种”方法,在确定【dp】P1982 小朋友的数字-LMLPHP后开始模数(于是就和大部分程序一样实际上不完全正确;但本题luogu数据(也许就是当年数据)真的非常不全面,就算很多小细节没有完全也能AC)

还有一件事:pas里面longint溢出没有报RE!90分的最后一个点WA就是因为溢出到负数!这操作很神奇

精简后的代码框架就是这样子的

05-15 08:07