小朋友的数字

题目链接

题目翻译：

每个小朋友有一个数字，构成一个数字序列a1,a2…an

我们定义“特征值”fi为a1~ai中的最大连续子段和

再定义“分数”si为1~i-1中最大的(sj+fj),特殊的,s1=f1,

要求输出最大的si

DP：

于是我们可以dp求出每个最大连续子段和作为特征值

然后按题意模拟一遍求出每个分数

状态定义：

dp[i]表示以i为结尾的最大子段和

方程

dp[i]=max(dp[i-1],0)+x; //连着/不连着前面

f[i]=max(f[i-1],dp[i]);

优化：

空间：

我们发现f[i]、dp[i]都是由f[i-1]、dp[i-1]转移来的，我们可以考虑将数组降一维于是空间复杂度就是常数级别的了

时间：

1.1e6的数据快读是有一定作用的

2.边读入边处理，减少常数

3.由于要用long long，取模运算很慢，可以考虑减少取模次数，当ans>1e17时再取模

#include<cstdio>

using namespace std;

#define int long long

#define N 1000010

#define INF 0x3f3f3f3f

const int ch_top=4e7+;

char ch[ch_top],*now_r=ch-,*now_w=ch-;

inline int read(){  //快读

    int f=;

    while(*++now_r<'') if(*now_r=='-') f=-;

    register int x=*now_r-'';

    while(*++now_r>='')x=(x<<)+(x<<)+*now_r-'';

    return x*f;

}

inline void write(int x){ //并没用什么卵用的快写

    if(x<){*++now_w='-',x=-x;}

    static char st[];static int top;

    while(st[++top]=''+x%,x/=);

    while(*++now_w=st[top],--top);

    *++now_w='\n';

}

int n,p,dp,ans1,ans;

bool flag;

#undef int

int main()

#define int long long

{

    fread(ch,,ch_top,stdin);//快读

    n=read(); p=read();

    int x,f;

    dp=f=read();

    ans1=f;ans=f*; //特殊处理第一个数

    /*ans1为第一个小朋友的分数,

    ans为其他小朋友的分数的最大值*/

    for(int i=;i<n;i++){

        x=read();

        dp=(dp>?dp:)+x;

        if(dp>f) f=dp;

        if(f>) ans=ans+f;

        if(ans>1e17) { ans%=p,flag=; }

        /*当ans为负时，一定不会是两个以上的

        负数之和,不会爆ll，若取过模，ans一定大于

        ans1，用一个flag记录*/

    }

    if(flag)write(ans%p);

    else{

        if(ans1>ans) ans=ans1;

        write(ans%p);

    }

    fwrite(ch,,now_w-ch,stdout);   //快写

    return ;

}

开O2 32ms ，大概是非打表提交的最优解

巴特西

【洛谷P1982】小朋友的数字

小朋友的数字

题目翻译：

DP：

优化：

最新文章

热门文章