NC16540. [NOIP2013]小朋友的数字
描述
有n 个小朋友排成一列。每个小朋友手上都有一个数字，这个数字可正可负。规定每个小朋友的特征值等于排在他前面（包括他本人）的小朋友中连续若干个（最少有一个）小朋友手上的数字之和的最大值。
作为这些小朋友的老师，你需要给每个小朋友一个分数，分数是这样规定的：第一个小朋友的分数是他的特征值，其它小朋友的分数为排在他前面的所有小朋友中（不包括他本人），小朋友分数加上其特征值的最大值。
请计算所有小朋友分数的最大值，输出时保持最大值的符号，将其绝对值对p 取模后输出。
输入描述
第一行包含两个正整数n、p，之间用一个空格隔开。
第二行包含n个数，每两个整数之间用一个空格隔开，表示每个小朋友手上的数字。
输出描述
输出只有一行，包含一个整数，表示最大分数对p取模的结果。
示例1
输入:
5 997 1 2 3 4 5
输出:
21
说明:
小朋友的特征值分别为1、3、6、10、15，分数分别为 1、2、5、11、21，最大值 21 对 997 的模是 21。示例2
输入:
5 7 -1 -1 -1 -1 -1
输出:
-1
说明:
小朋友的特征值分别为-1、-1、-1、-1、-1，分数分别为-1、-2、-2、-2、-2，最大值-1 对 7 的模为-1，输出-1。C++14(g++5.4) 解法, 执行用时: 352ms, 内存消耗: 16196K, 提交时间: 2020-09-01 11:58:06
#include<bits/stdc++.h>
using namespace std;
long long da[1000001],fen[1000001];
int main(){
long long n,p,s=0;
cin>>n>>p;
da[0]=-9000000000000000000;
for(long long i=1;i<=n;i++){
long long a;
cin>>a;
s=s+a;
da[i]=max(da[i-1],s);
if(s<0)s=0;
}
fen[1]=da[1]%p;
fen[2]=(da[1]+fen[1])%p;
for(long long i=3;i<=n;i++){
fen[i]=max(fen[i-1],fen[i-1]+da[i-1])%p;
}
if(fen[1]>0)cout<<fen[n]<<endl;
else cout<<max(fen[n],fen[1])<<endl;
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 331ms, 内存消耗: 10116K, 提交时间: 2022-09-10 23:39:48
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int n,p,a;
cin>>n>>p>>a;
long long s=max(a,0),x=a,maxn=a*2;
bool flag=a>0&&n>1;
for(n-=2;n-->0;s=max(s,(long long)0)){
int c;
cin>>c;
s+=c;
maxn+=max(x=max(x,s),(long long)0);
if(flag){
maxn%=p;
}else if(maxn>a){
flag=1;
}
}
maxn=(flag?maxn:a);
if(maxn<0){
cout<<'-';
}
cout<<abs(maxn)%p;
return 0;
}