P1115 最大子段和 分治

· · 个人记录

前言

最近听了去年提高组秋令营，听说一条普及- 的题目可以用到分治O(nlogn)，然后方法又特别像某些高级题目的做法，顺便看题解前面好像没有，于是就把我的第一次洛谷题解交给了她。。。

e.咳咳我们转入正题。

我们怎么用分治？

· 我们发现，如果由两个小区间合成一个大区间，答案可能在哪些地方呢？

  1. 是整个区间的前缀最大值

  2. 是整个区间的后缀最大值

  3. 是跨越中点的一段区间

  4. 原来是上面三种情况，但由于经过合并已经并到里面去的区间。（关于“里面”的解释）

这个4就是里面啦啦啦啦

所以，我们用一个结构体存下这所有东西先。。

struct xx{
    int l,r,md,sum,ans;
    xx(int ll,int rr,int m,int s,int a){
        l=ll;r=rr;md=m;sum=s;ans=a;
    }//ans是区间的答案，sum是区间总和便于下一步
};

然后对于每种答案型的继承

  1. 有我画的两种情况（绿色！）
max(t1.l,t1.sum+t2.l)

  1. 同理（雷姆蓝！）

  2. 黄色很好想吧

t1.r+t2.l
  1. 由于我们对每个区间都记录了最大值，继承子区间,并和新的区间参数比较
max(max(max(t3.l,t3.r),t3.md),max(t1.ans,t2.ans));

max打得我累死了呼呼

呦西，这样，一份超级简单的代码就新鲜出炉啦

//P1115 最大子段和分治
#include<iostream>
using namespace std;
#define N 200005

struct xx{
    int l,r,md,sum,ans;
    xx(int ll,int rr,int m,int s,int a){
        l=ll;r=rr;md=m;sum=s;ans=a;
    }
};

int n,a[N];

xx solve(int l,int r){
    if(l==r)return xx(a[l],a[l],a[l],a[l],a[l]);
    int md=(l+r)>>1;
    xx t1=solve(l,md),t2=solve(md+1,r);
    xx t3=xx(max(t1.l,t1.sum+t2.l),max(t2.r,t2.sum+t1.r),t1.r+t2.l,t1.sum+t2.sum,0);
    t3.ans=max(max(max(t3.l,t3.r),t3.md),max(t1.ans,t2.ans));
    return t3;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    xx ans=solve(1,n);
    cout<<ans.ans<<endl;
    return 217527; //反抄袭大法好并滑稽保命
}
//made by jiangji2

就这样吧，第一次写题解，谢谢您的耐心观看QWQ！