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

· · 题解

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

思路

显然，这道题目需要先对于每一个节点求出最大子段和，做一遍 dp。

接下来，只需要线性扫描，求出每一个小朋友分数的前缀最大值即可。

时间复杂度 O(n)。

需要注意的是本题的数据范围，需要开 __int128。

AC Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
__int128 read() {
    __int128 x = 0;
    int w = 0; 
    char ch;
    while (!isdigit(ch)) { 
        w |= ch == '-'; ch = getchar(); 
    }
    while (isdigit(ch)) 
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return w ? -x : x;
}

void out(__int128 x) {
    if (x < 0) {putchar('-');x *= -1;}
    if (x > 9) out(x / 10);
    putchar(x % 10 + '0');
}

long long n;
__int128 p,a[maxn],dp[maxn],f[maxn],ans[maxn],anss;

inline __int128 abss(__int128 x){
    if(x>=0)return x;
    return -x;
}

int main(){
    scanf("%lld",&n);
    p = read();
    for(long long i = 1;i <= n;i++) a[i] = read();
    f[1] = a[1],ans[1] = a[1];
    for(long long i = 2;i <= n;i++){
        f[i] = max(a[i],f[i-1]+a[i]);
        ans[i] = max(ans[i-1],f[i]);
    }
    if(n == 1){
        out(ans[1]%p);
        return 0;
    }
    dp[1] = ans[1],dp[2] = ans[1] + ans[1];
    anss = max(dp[1],dp[2]);
    for(long long i = 3;i <= n;i++) dp[i] = max(dp[i-1],dp[i-1]+ans[i-1]),anss = max(dp[i],anss);
    if(anss < 0) printf("-");
    __int128 o = abss(anss)%p;
    out(o);
    return 0;
}