题目总体意思就是找到没一个小朋友的特征值,这个特征值就是包括这第 iii 小朋友在内的 1−i1-i1−i 中的一段连续的小朋友手上拿的卡片 的最大值
也就是一个最大子段和.然后这个分数则是第 iii 个小朋友之前不包括第 iii 个小朋友在内的 1−1-1− ( i−1i-1i−1 )的小朋友的分数加上特征值的最大值
题目让我们求所有小朋友中的最大分数
其实挺好理解的
最大子段和我们可以从 1−n1-n1−n 直接扫过去,设 areaareaarea 为当前某一段子段和.然后从 111 开始一个个加到 areaareaarea 里,然后最大值 =max=max=max (最大值, areaareaarea )
然后我们用一个数组,分别存下每一个小朋友所对应的特征值(最大子段和), tzztzztzz [ iii ] === 当前最大值
然后如果 area<0area<0area<0 ,这个时候前面这个子段肯定没用了,所以 area=0area=0area=0 ;
求出所有小朋友的特征值后,去算分数
然而这里的 nnn 是小于 1e61e61e6 ,其他数字不超过 1e91e91e9 .相信正常人都知道应该写高精了.
但是高精一般会让我们直接输出解,而这里没有,所以不是高精.
第一个小朋友的分数 === 特征值,第二个小朋友的分数 === 第一个小朋友的分数 +++ 第一个小朋友的最大值
第三个小朋友 === 前面两个小朋友分数与特征值的最大. 第四个 === 前面三个
从这里我们可以看出这个小朋友的分数是从前面取最大值,所以说分数一定是大于或者是等于前面的分数
这样就可以免掉高精比较了
因为这里的第一个数是肯定不会大于 1e91e91e9 的,所以如果有数字是大于 1e91e91e9 的就可以直接 modmodmod 了(这里我还是不懂,半懂不懂的)
这里可以判断一个数是否大于第一个数,如果没有 modmodmod 的的话直接输出 fff [ nnn ],有的话要 maxmaxmax ( fff [ 111 ], fff [ nnn ]),因为取余了
然后这样子就可以避免高精加了
开 longlonglong longlonglong