小朋友的数字(codevs 3293)
2024-08-30 23:21:24
题目描述 Description
有n个小朋友排成一列。每个小朋友手上都有一个数字,这个数字可正可负。规定每个小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最少有一个)小朋友手上的数字之和的最大值。
作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的:第一个小朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人),小朋友分数加上其特征值的最大值。
请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对p取模后输出。
输入描述 Input Description
第一行包含两个正整数n、p,之间用一个空格隔开。
第二行包含n个数,每两个整数之间用一个空格隔开,表示每个小朋友手上的数字。
输出描述 Output Description
输出只有一行,包含一个整数,表示最大分数对p取模的结果。
样例输入 Sample Input
[Sample 1]
5 997
1 2 3 4 5
[Sample 2]
5 7
-1 -1 -1 -1 -1
样例输出 Sample Output
[Sample 1]
21
[Sample 2]
-1
数据范围及提示 Data Size & Hint
【样例说明】
样例1小朋友的特征值分别为1、3、6、10、15,分数分别为1、2、5、11、21,最大值21对997的模是21。
样例2小朋友的特征值分别为-1、-1、-1、-1、-1,分数分别为-1、-2、-2、-2、-2,最大值-1对7的模为-1,输出-1。
【数据范围】
对于50%的数据,1≤n≤1,000,1≤p≤1,000所有数字的绝对值不超过1000;
对于100%的数据,1≤n≤1,000,000,1≤p≤10^9,其他数字的绝对值均不超过10^9。
/*
看数据范围,感觉long long应该可以过,但是不是道为什么WA了两个点,剩下两个点有个小技巧。
首先模拟最大子段和求出te数组,求fen数组的时候,我们发现,除了fen[1]和fen[2],剩下的保证不下降,
那么当剩下的都比fen[1]小的时候,我们可以直接输出fen[1],不会越long long,否则输出fen[n],因为
此时fen[n]一定是最大的。
*/
#include<cstdio>
#include<iostream>
#define M 1000010
#define INF 1000000000000000000LL
#define LL long long
using namespace std;
LL te[M],fen[M],mod;int n;
bool flag=false;
LL read()
{
char c=getchar();LL num=,flag=;
while(c<''||c>''){if(c=='-')flag=-;c=getchar();}
while(c>=''&&c<=''){num=num*+c-'';c=getchar();}
return num*flag;
}
int main()
{
scanf("%d",&n);mod=read();
LL maxn=read();te[]=maxn;
LL s=maxn;
for(int i=;i<=n;i++)
{
LL x=read();
s=max(s+x,x);
te[i]=max(s,maxn);
maxn=max(maxn,te[i]);
}
fen[]=te[];fen[]=fen[]*;
for(int i=;i<=n;i++)
{
if(te[i-]>)
{
fen[i]=te[i-]+fen[i-];
if(fen[i]>fen[])
{
flag=;
fen[i]%=mod;
}
}
else fen[i]=fen[];
}
if(flag)cout<<fen[n]%mod;
else cout<<fen[]%mod;
return ;
}
最新文章
- 【Beta】第七次任务发布
- MSSQL&mdash;字符串分离(Split函数)
- Oracle数据库中创建表空间语句
- Div 自适应屏幕大小
- spring 的properties解析
- Can jxta be used to develop online card game (p2p style)?
- BZOJ2191Splite
- C语言基础课程 第三课 ADB(Android Debug Bridge)的使用
- Day9 - Python 多线程、进程
- 使用xml及java代码混合的方式来设置图形界面
- php基础教程笔记2
- ADB抓取内存命令
- Sql Server查询性能优化之不可小觑的书签查找
- es6 import export 引入导出变量方式
- C/C++的64为长整型数的表示
- 奇怪吸引子---ChenCelikovsky
- lua闭包
- 5 -- Hibernate的基本用法 --3 Hibernate的体系结构
- Mac下像Windows那样带有预览图的快速切换-HyperSwitch
- Android 最早使用的简单的网络请求
热门文章
- 使用nginx加zuul配置
- [C++ 多线程] 学习前瞻
- tablespace monitor shell for windows
- Linux系统下强制踢掉登录用户
- 258 Add Digits 各位相加
- [ USACO 2017 FEB ] Why Did the Cow Cross the Road III (Gold)
- spark查看stage和tasks信息
- [转]汇编语言:MOVSB,MOVSW,MOVSD
- (转)淘淘商城系列——商品搜索功能Service实现
- iOS,Core Animation--负责视图的复合功能