【dp】P1982 小朋友的数字

有趣的细节题目

题目描述

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

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

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

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

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

特征值：

算法一：

静态前缀和。

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

由此引申到算法二

算法二：

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

算法三：

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

分数：

由题面可以得到；。并且在 $[2,n]$ 中维持不下降的性质（当 $special[1]<0$ 时，答案可能是 $score[n]$ ；当 $special[1]>0$ ,答案必为 $score[n]$ ）。那么就容易得到 $ans=max\{score_1,score_n\}$ 。因为计算过程中有可能爆精度，但又不能马上模，一种是C++中__int128，另一种是当 $score[i]>score[1]$ 时就能确定 $ans=score[n]$ （但是！但是！这个方法虽然被很多AC数据采用，但是遇到如：8 66 -511657297 151810723 -588294472 -271526366 58051666 -792123397 -76376854 -36217375 此数据时会计算出错误答案！）。如果坚持正解的话，还是用大整数或者__int128（C++）吧。

那么怎么计算 $score$ 呢？

题目的计算方法是 $score[i]=\max\{score[j]+special[j]\}(j\in[1,i))$

我们可以发现， $score[i-1]=\max\{score[j]+special[j]\}(j\in[1,i-1))$

所以当计算 $score[i]$ 时，我们只需要比较 $score[i-1]$ 与 $score[i-1]+special[i-1]$ ，即看 $special[i-1]$ 的正负

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

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

另外，模数是个麻烦的问题。最早的时候，我是输入就模、计算就模，但是我忽略了一个非常明显的问题：最大值模后不一定最大，就是说这样计算出来的只是模后最大值。所以用以上的“另一种”方法，在确定 $ans=score[n]$ 后开始模数（于是就和大部分程序一样实际上不完全正确；但本题luogu数据（也许就是当年数据）真的非常不全面，就算很多小细节没有完全也能AC）

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

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

巴特西

【dp】P1982 小朋友的数字

题目描述

最新文章

热门文章