【模拟?】小朋友的数字模拟

小朋友的数字题目

有 n n个小朋友排成一列。每个小朋友手上都有一个数字，这个数字可正可负。规定每个小朋友的特征值等于排在他前面（包括他本人）的小朋友中连续若干个（最少有一个）小朋友-手上的数字之和的最大值.
作为这些小朋友的老师，你需要给每个小朋友一个分数，分数是这样规定的：第一个小朋友的分数是他的特征值，其它小朋友的分数为排在他前面的所有小朋友中（不包括他本人），小朋友分数加上其特征值的最大值。
请计算所有小朋友分数的最大值，输出时保持最大值的符号，将其绝对值对 pp 取模后输出。

输入

【【模拟?】小朋友的数字】第一行包含两个正整数 n,pn,p，之间用一个空格隔开。
第二行包含 nn 个数，每两个整数之间用一个空格隔开，表示每个小朋友手上的数字。

输出

一个整数，表示最大分数对 p p取模的结果。

输入样例 #1

5 997 1 2 3 4 5

21

输入

5 7 -1 -1 -1 -1 -1

输出

-1

说明样例1:

小朋友的特征值分别为 1,3,6,10,151,3,6,10,15，分数分别为 1,2,5,11,211,2,5,11,21，最大值 2121对 997997 的模是 2121。

样例2:

小朋友的特征值分别为-1,-1,-1,-1,-1分数分别为-1,-2,-2,-2,-2最大值-1对 77 的模为-1，输出-1。

数据

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

解题思路其实这道题就是一道模拟题，判断是否为特征值最优的，然后就可以得出最优的分数即可.
程序如下

#include #include #include #include #define ll long long using namespace std; ll n,moduls,s,a[1000001],Final_value; ll features_max,statistics_f[1000001]; ll Fraction_max,statistics_s[1000001]; int main() { features_max = -2147483647; scanf("%lld %lld",&n,&moduls); for(ll i = 1; i <= n; ++i) { scanf("%lld",&s); if(a[i - 1] > 0) a[i] = a[i - 1] + s; //算出分数 elsea[i] = s; features_max = max(features_max, a[i]); //求出当前特征值 statistics_f[i] = features_max % moduls; } Final_value = https://www.it610.com/article/statistics_f[1]; //初始值 statistics_s[1] = statistics_f[1]; //初始值 Fraction_max = -2147483647; //初始值 for(ll i = 2; i <= n; ++i) { Fraction_max = max(Fraction_max, statistics_f[i - 1] + statistics_s[i - 1]); //算出目前的分数 statistics_s[i] = Fraction_max; //当前的分数 if(Final_value <= Fraction_max) Final_value = Fraction_max % moduls; //算出最大的分数 } printf("%lld",Final_value); return 0; }