[NOIP2013 普及组] 小朋友的数字
思路
题中“特征值”是指前面最大的一段数字之和,即以该数结尾的序列的最大子段和,用\(DP\)解决。至于得分,可以从左往右扫一遍,扫的过程中维护一个分数\(+\)特征值的最大值即可。
另外,此题数据会很大,\(long\) \(long\)都不行,可以打个高精或使用__\(int128\)
代码
#include<bits/stdc++.h>
#define MAXN 1000010
#define INF 2000000000
#define int __int128
using namespace std;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
int n,p,num[MAXN],te[MAXN],fen[MAXN],sum[MAXN],now=-INF,ans=-INF;
int mid[MAXN];
signed main()
{
n=read();
p=read();
int nowm=-INF;
for(int i=1;i<=n;i++)
{
num[i]=read();
if(i==1)mid[i]=num[i];
else mid[i]=max(num[i],mid[i-1]+num[i]);
}
for(int i=1;i<=n;i++)
{
nowm=max(nowm,mid[i]);
te[i]=nowm;
}
for(int i=1;i<=n;i++)
{
if(i==1)fen[i]=te[i];
else fen[i]=now;
now=max(now,fen[i]+te[i]);
ans=max(ans,fen[i]);
}
if(ans>=0)write(ans%p);
else write(-1*((-1*ans)%p));
return 0;
}
标签:普及,ch,NOIP2013,int,MAXN,小朋友,INF,define
From: https://www.cnblogs.com/huled/p/16773205.html