题目链接
一道坑点比较多的简单动规。

80分

根据题意,可以把每个小朋友的特征值转化为最长连续子段和。
然后开一下long long,且按照题意生推f数组即可.
第一个坑点就是,特征值是可以要自己的也可以不要,因此需要比较两次。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<limits.h>
using namespace std;
typedef long long ll;
ll ans,n,p,a[1000005],dp[1000005],f[1000005];
bool flag=false;
inline ll max(ll cp1,ll cp2)
{
    return cp1>cp2?cp1:cp2;
}
int main()
{
    ans=-INT_MAX;         
    dp[0]=-INT_MAX;
    f[0]=-INT_MAX;
    ios::sync_with_stdio(false);
    cin>>n>>p;
    for(register int i=1;i<=n;i++)
        cin>>a[i];
    dp[1]=a[1];
    for(register int i=2;i<=n;i++)
    {
        dp[i]=max(a[i],dp[i-1]+a[i]);
    }
    for(register int i=2;i<=n;i++)
    {
        dp[i]=max(dp[i],dp[i-1]);
    }
    f[1]=dp[1];
    f[2]=a[1]+dp[1];
    for(register int i=3;i<=n;i++)
    {
        f[i]=max(f[i-1],dp[i-1]+f[i-1]);
        //cout<<f[i]<<endl;
    }
    for(register int i=1;i<=n;i++)
    {
        ans=max(ans,f[i]);
    }
    cout<<ans%p;
    return 0;
}

100分

这个时候就涉及到了题目的第二个坑点:模p。
由于数据很大,所以说上面的比较方法会炸。
那么很明显需要边模边加。但是这样问题就来了,最后ans不一定是实际上最大的分数的取模结果(因为取了模),那么开始思考如何解决这个问题。根据题目要求,我们发现分数在[2,n]上具有不严格的单调性!然后就可以分类讨论一下。
我们发现,当dp[1]<0时,f[1]就肯定是大于f[2]的,dp[1]>0反之.
因此结果不是第一个就是最后一个。因此更新的时候,就可以比较一下f[i-1]和f[1]的大小,然后标记一下输出f[n]还是f[i]就好辣。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<limits.h>
using namespace std;
typedef long long ll;
ll ans,n,p,a[1000005],dp[1000005],f[1000005];
bool flag=false;
inline ll max(ll cp1,ll cp2)
{
    return cp1>cp2?cp1:cp2;
}
int main()
{
    ans=-INT_MAX;         
    dp[0]=-INT_MAX;
    f[0]=-INT_MAX;
    ios::sync_with_stdio(false);
    cin>>n>>p;
    for(register int i=1;i<=n;i++)
        cin>>a[i];
    dp[1]=a[1];
    for(register int i=2;i<=n;i++)
    {
        dp[i]=max(a[i],dp[i-1]+a[i]);
    }
    for(register int i=2;i<=n;i++)
    {
        dp[i]=max(dp[i],dp[i-1]);
    }
    f[1]=dp[1];
    f[2]=a[1]+dp[1];
    ans=max(f[1],f[2]);
    for(register int i=3;i<=n;i++)
    {
        if(f[i-1]>f[1]) 
            flag=true;//分类特判
        if(flag)
        {
            f[i]=(f[i-1]%p+dp[i-1]%p)%p;
        }
        else
        {
            f[i]=max(dp[i-1]+f[i-1],f[i-1]);
        }
         ans=max(ans,f[i]);
    }
    if(flag)
        cout<<f[n]%p;
    else
        cout<<ans%p;
    return 0;
}