题解：P1982 [NOIP2013 普及组] 小朋友的数字

· · 题解

solution

动态规划问题。

设 a_i 表示 i 的数字，q_i 表示以 i 结尾的最大子段和，初始化 q_1=a_1，转移 q_i = \max(a_i, q_{i-1}+a_i)。

设 t_i 表示前 i 个数中以任意数结尾的最大子段和，也是 i 的特征值，初始化 t_1=a_1，则 t_i = \max(t_{i-1}, q_i)。

设 f_i 表示 i 的分数，题目说第一个人的分数是第一个人的特征值，故初始化 f_1=t_1，考虑转移。

对于 i 的分数，可以是前 i-2 个人中分数加上其特征值的最大值，也就是第 i-1 个人的分数，即 f_{i-1}，也可以是第 i-1 个人的分数加上其特征值，即 f_{i-1}+t_i，f_i = \max(f_{i-1}, f_{i-1}+t_{i-1})。

这里要特判 f_2=f_1+t_1，否则可能会算成 f_1。

结果会很大，并且没办法随时取模，所以要开 __int128。

code

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
long long n, p, a[N], q[N], t[N];
__int128 f[N], ans;
void out (__int128 x) {
    if (x>9)
        out(x/10);
    putchar(x%10+'0');
}
int main () {
    cin >> n >> p;
    for (int i=1; i<=n; ++i)
        cin >> a[i];
    ans=f[1]=t[1]=q[1]=a[1];
    for (int i=2; i<=n; ++i)
        q[i]=max(q[i-1]+a[i], a[i]),
        t[i]=max(t[i-1], q[i]),
        f[i]=(i==2?2*f[1]:max(f[i-1], f[i-1]+t[i-1])),
        ans=max(ans, f[i]);
    if (ans<0)
        cout << '-',
        ans=-ans;
    out(ans%p);
    return 0;
}