P1982 小朋友的数字
2024-08-31 07:22:06
题目描述
有 n 个小朋友排成一列。每个小朋友手上都有一个数字,这个数字可正可负。规定每个
小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最少有一个)小朋
友手上的数字之和的最大值。
作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的:第一个小
朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人),
小朋友分数加上其特征值的最大值。
请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对 p 取模后
输出。
输入输出格式
输入格式:
输入文件为 number.in。
第一行包含两个正整数 n、p,之间用一个空格隔开。
第二行包含 n 个数,每两个整数之间用一个空格隔开,表示每个小朋友手上的数字。
输出格式:
输出文件名为 number.out。
输出只有一行,包含一个整数,表示最大分数对 p 取模的结果。
输入输出样例
输入样例#1:
5 997
1 2 3 4 5
输出样例#1:
21
输入样例#2:
5 7
-1 -1 -1 -1 -1
输出样例#2:
-1
说明
Case 1:
小朋友的特征值分别为 1、3、6、10、15,分数分别为 1、2、5、11、21,最大值 21
对 997 的模是 21。
Case 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
我们用dptz表示特征的最大值。
用dpfs表示分数的最大值
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define lli long long int
using namespace std;
const lli MAXN=;
void read(lli &n)
{
char c='+';lli x=,flag=;
while(c<''||c>''){c=getchar();if(c=='-')flag=-;}
while(c>=''&&c<=''){x=x*+c-;c=getchar();}
n=x*flag;
}
lli n,mod;
lli dptz[MAXN];
lli dpfs[MAXN];
lli a[MAXN];
lli now=;// 当前最大字段和
lli ans=-;
int main()
{
read(n);read(mod);
for(lli i=;i<=n;i++)
read(a[i]);
dptz[]=a[];
for(lli i=;i<=n;i++)
{
now+=a[i];
dptz[i]=now;
if(now<)
now=;
}
for(lli i=;i<=n;i++)
dptz[i]=max(dptz[i],dptz[i-]);
dpfs[]=dptz[];
dpfs[]=dpfs[]+dptz[];
bool flag=;
for(lli i=;i<=n;i++)
{
dpfs[i]=dpfs[i-];
if(dptz[i-]>)
dpfs[i]+=dptz[i-];
if(dpfs[i]>dpfs[])flag=;
if(flag==)
dpfs[i]=dpfs[i]%mod;
}
if(flag==)
printf("%lld",dpfs[n]);
else
printf("%lld",dpfs[]);
return ;
}
最新文章
- LeetCode之171. Excel Sheet Column Number
- web压力测试工具
- maven学习手记 - 3
- 分享一些前端chm文档
- Python调试工具-Spyder
- 线上问题:如何定位解决CPU高占有率
- 禁止选择文本和禁用右键 v1.0
- NodeJS学习笔记—2.AMD规范
- Json对象直接存取数据库
- Qt编程之对QGraphicsItem点击右键弹出菜单
- Java EE (1) -- Java EE 6 Web Component Developer Certified Expert(1z0-899)
- erlang进程与操作系统线程
- css3特效详解
- Oracle dba_tablespace_usage_metrics 视图 查看表空间 说明
- scala的reduce
- PHP中feof()函数的猜测
- 7-6 Bandwidth UVA140
- 主机在无线网络的情况下,设置centos7.2虚拟机网络联通
- [Windows Azure] Learn SQL Reporting on Windows Azure (9-Step Tutorial)
- LeetCode: Binary Tree Preorder Traversal 解题报告
热门文章
- js DOM 节点树 设置 style 样式属性
- java这个404你能解决吗?
- solr的学习
- CF319E Ping-Pong 线段树 + vector + 思维
- CodeForces 245C-Game with Coins
- 排序算法总结(C++)
- 利用Flask-SQLAlchemy提供的paginate()方法实现博客文章的分页显示
- bzoj 2654 &;&; bzoj 3675 总结
- java中Date与String转化 string转float
- JAVA数据库连接的另一种实现及简单的数据插入及显示