AcWing 455. 小朋友的数字
原题链接
中等
作者:
y总的小迷弟
,
2023-10-10 19:29:18
,
所有人可见
,
阅读 67
//这是一篇部分题解;
//就dp而言,这是一道非常基础的dp,但就题面的抽象程度和数据的恶心程度来讲,非常难;
//首先,这里的特征值定义为:i及其之前的最大子段和,不能直接用f[i]!!!
//并且会爆ll,反正80pts也不错了,高精度就不写了;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, p;
ll a[1000010];//原数组
ll f[1000010];//子段和数组
ll q[1000010];//最大子段和数组
ll num[1000010];//分数数组
int main()
{
cin >> n >> p;
for(int i = 0;i <= n;i++)
q[i] = -1e18;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
f[i] = a[i];
f[i] = max(f[i], f[i - 1] + f[i]);
q[i] = max(q[i - 1], f[i]);
}//预处理
ll maxn = -1e18;//“小朋友分数加上其特征值的最大值”
ll ans = -1e18;
for(int i = 1;i <= n;i++)
{
if(i == 1)
{
num[i] = a[i];
maxn = num[i] + q[i];
}
else
{
num[i] = maxn;
maxn = max(maxn, num[i] + q[i]);
}
ans = max(ans, num[i]);
}
cout << ans % p << endl;
return 0;
}