求助线段树最大子段和
  • 板块学术版
  • 楼主Eleveslaine
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/6/5 22:30
  • 上次更新2023/10/23 13:52:04
查看原帖
求助线段树最大子段和
450246
Eleveslaine楼主2023/6/5 22:30

P4513 or GSS1 or GSS3

问一下这种做法对不对。

线段树的每个结点维护区间边界 [l,r][l,r],最大子段和 sumsum,在最大子段左侧的区间和 s1s_1,在最大子段右侧的区间和 s2s_2(即 s1+sum+s2=[l,r]s_1+sum+s_2=[l,r] 区间和)。

在 update/pushup 时,取得 s1,A,s2,s3,B,s4s_1,A,s_2,s_3,B,s_4 六个值,分别对应左孩子和右孩子的 s1,sum,s2s_1,sum,s_2(有点重名了抱歉)。 然后分情况计算出结点 kk 的 s1,sum,s2s_1,sum,s_2。

这部分的代码:

LaCampanella ans; // 自定义结构体
ans.l=L.l,ans.r=R.r;
ans.sum=-inf;
int A=L.sum,
    B=R.sum,
    s1=L.s1,
    s2=L.s2,
    s3=R.s1,
    s4=R.s2;
if(A>ans.sum)
{
    ans.sum=A;
    ans.s1=s1,ans.s2=s2+s3+B+s4;
}
if(B>ans.sum)
{
    ans.sum=B;
    ans.s1=s1+A+s2+s3,ans.s2=s4;
}
if(A+s2+s3+B>ans.sum)
{
    ans.sum=A+s2+s3+B;
    ans.s1=s1,ans.s2=s4;
}
if(A+s2+s3>ans.sum)
{
    ans.sum=A+s2+s3;
    ans.s1=s1,ans.s2=B+s4;
}
if(s2+s3+B>ans.sum)
{
    ans.sum=s2+s3+B;
    ans.s1=s1+A,ans.s2=s4;
}
if(A+s2+s3+B+s4>ans.sum)
{
    ans.sum=A+s2+s3+B+s4;
    ans.s1=s1,ans.s2=0;
}
if(s1+A+s2+s3+B>ans.sum)
{
    ans.sum=s1+A+s2+s3+B;
    ans.s1=0,ans.s2=s4;
}
return ans;

然后现在只有 99 分。问一下这个做法是否正确,或者是我写挂了/kk
完整代码。

QAQ

2023/6/5 22:30
加载中...