本文共 1213 字，大约阅读时间需要 4 分钟。

$$小朋友的数字$$

题目链接：$/$

题目

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

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

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

输入

第一行包含两个正整数 $n$、$p$，之间用一个空格隔开。
第二行包含 $n$ 个数，每两个整数之间用一个空格隔开，表示每个小朋友手上的数字。

输出

输出只有一行，包含一个整数，表示最大分数对 $p$ 取模的结果。

样例输入1

5 997 1 2 3 4 5 

样例输出1

21

样例输入2

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

样例输出

-1

思路

这道题就是一道模拟。
我们可以用最大连续子序列求出每个人的特征值，再按照题目求出每个人的分数。
我们再找到最大的分数，就是答案了。
（记得取模）

代码

#include<cstdio>#define ll long long#define max(x, y) (x) > (y) ? (x) : (y)using namespace std;ll n,p,s[10000001],t[10000001],f[10000001],k[10000001],maxn=-2147483647,x,ans;int main(){   	scanf("%lld %lld", &n, &p);//读入    for(ll i = 1; i <= n; i ++)    {   		scanf("%lld", &x);//读入		if(s[i - 1] > 0)  s[i] = s[i - 1] + x;//最大连续子序列			else  s[i] = x;		maxn = max(s[i], maxn);//求最大值		t[i] = maxn % p;//标记    }    ans = t[1];//初始化    f[1] = t[1];//初始化    maxn = -2147483647;//初始化    for(ll i = 2; i <= n; i ++)    {   		maxn = max(maxn, t[i - 1] + f[i - 1]);//求出每个人的分数		f[i] = maxn;//赋值		if(ans < maxn) ans=maxn % p;//求出最大值    }    printf("%lld", ans);//输出    return 0;}