精华内容
下载资源
问答
  • 最大连续区间和问题

    2017-08-27 16:40:00
    最大连续区间和,可以有很多种方法实现,其中最常见的是运用一维前缀和还有动态规划来解决的; 代码如下: /* @theme:最大连续区间和的算法 @writer:pprp @declare:有几种方法 @date:2017/8/27 */ #...

    2017-08-27 16:38:47

    writer:pprp

    最大连续区间和,可以有很多种方法实现,其中最常见的是运用一维前缀和还有动态规划来解决的;

    代码如下:

    /*
    @theme:最大连续区间和的算法
    @writer:pprp
    @declare:有几种方法
    @date:2017/8/27
    */
    
    #include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 10000;
    int a[maxn];
    int sum[maxn];
    int ans;
    
    int main()
    {
        //法一、暴力解,这就不写了
        //法二、采用一维前缀和
    
        ios::sync_with_stdio(false);
        int N;
        cin >> N;
        for(int i = 0 ; i < N ; i++)
        {
            cin >> a[i];
        }
        sum[0] = a[0];
        for(int i = 1 ; i < N ; i++)
            sum[i] = sum[i-1] + a[i];
    
        ans = 0;
        for(int i = 0 ; i < N ; i++)
            for(int j = i+1 ; j < N ; j++)
                ans = max(ans,sum[j]-sum[i-1]);
                
                cout << ans << endl;
        //法三、动态规划
        int ans = 0;
        int tmp = 0;
        for(int i = 0 ; i < N ; i++)
        {
              tmp = max(tmp,0) + a[i];
              ans = max(ans, tmp);
        }
        
        cout << ans << endl;
        //总结,一般都采用的是第三种方法,比较省时间和空间
        return 0;
    }

     

    转载于:https://www.cnblogs.com/pprp/p/7440729.html

    展开全文
  • 【题意】给定一个点求其所在最大连续区间的长度。 【方法】维护三个变量, pre[i]表示线段树结点i所代表区间的最大连续前缀, suf[i]表示线段树结点i所代表区间的最大连续后缀, maxLen[i]表示线段树结点i所代表...

    【传送门】Tunnel Warfare

    【题意】给定一个点求其所在最大连续区间的长度。

    【方法】维护三个变量,

    pre[i]表示线段树结点i所代表区间的最大连续前缀,

    suf[i]表示线段树结点i所代表区间的最大连续后缀,

    maxLen[i]表示线段树结点i所代表区间的最大连续区间长度。

    【模板】

    #include <iostream>
    #include <cstdio>
    #include <stack>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    const int maxn = 50000 + 100;
    
    int n,q;
    
    int s[maxn<<2],e[maxn<<2];
    int pre[maxn<<2], suf[maxn<<2], maxLen[maxn<<2];
    
    void build(int rt, int l, int r){
        s[rt] = l;
        e[rt] = r;
        pre[rt] = suf[rt] = maxLen[rt] = r - l + 1;
        int mid = (l + r) >> 1;
        if(l != r){
            build(rt<<1 , l, mid);
            build(rt<<1|1, mid+1, r);
        }
        
    }
    
    void pushUp(int rt){
        pre[rt] = pre[rt<<1];
        suf[rt] = suf[rt<<1|1];
        maxLen[rt] = max(maxLen[rt<<1] , maxLen[rt<<1|1]);
        maxLen[rt] = max(maxLen[rt] , suf[rt<<1] + pre[rt<<1|1]);
        if(pre[rt<<1] == e[rt<<1] - s[rt<<1] + 1)    pre[rt] += pre[rt<<1|1];
        if(suf[rt<<1|1] == e[rt<<1|1] - s[rt<<1|1] + 1) suf[rt] += suf[rt<<1];
    }
    
    void update(int rt, int k, int v){
        if(s[rt] == k && e[rt] == k){
            pre[rt] = suf[rt] = maxLen[rt] = v;
            return ;
        }
        if(s[rt] == e[rt] ){
            return ;
        }
        
        int mid = (s[rt] + e[rt]) >> 1;
        if(k > mid)    update(rt<<1|1 , k , v);
        else update(rt<<1, k , v); 
        pushUp(rt);
    }
    
    int query(int rt , int k){
        if(maxLen[rt] == 0 || maxLen[rt] == e[rt] - s[rt] +1){
            return maxLen[rt];
        }
        
        int mid = (e[rt] + s[rt]) >> 1;
        
        if(k <= mid){
            if( k >= e[rt<<1] - suf[rt<<1] + 1)    return suf[rt<<1] + pre[rt<<1|1];
            else query(rt<<1 , k);
        }
        else{
            if(k <= s[rt<<1|1] + pre[rt<<1|1] - 1)    return suf[rt<<1] + pre[rt<<1|1];
            else query(rt<<1|1, k);
        }
    }
    
    int main(){
        char op[2];
        while(scanf("%d%d",&n,&q) != EOF){
            build(1,1,n);
            stack<int> s;
            int x;
            while(q--){
                scanf("%s",op);
                if(op[0] == 'D'){
                    scanf("%d",&x);
                    update(1,x,0);
                    s.push(x);
                }
                else if(op[0] == 'Q'){
                    scanf("%d",&x);
                    printf("%d\n",query(1,x));
                }
                else if(op[0] == 'R'){
                    x = s.top();
                    s.pop();
                    update(1,x,1);
                }
            }
    
        }
        return 0;
    }

     

    转载于:https://www.cnblogs.com/czsharecode/p/9863441.html

    展开全文
  • purplest ...最大连续区间和的算法总结 最大连续区间和是一个经典的问题。给定一个长度为n的序列a[1],a[2]...a[n-1],a[n],求一个连续的子序列a[i],a[i+1]...a[j-1],a[j],使得a[i]+a[i+1]......

    转载自:http://www.cppblog.com/purplest/archive/2013/03/04/198199.html

    purplest

    最大连续区间和是一个经典的问题。给定一个长度为n的序列a[1],a[2]...a[n-1],a[n],求一个连续的子序列a[i],a[i+1]...a[j-1],a[j],使得a[i]+a[i+1]...a[j-1]+a[j]最大。

    ①最简单最容易想到的就是根据定义来枚举。
    枚举上下界{i,j | 0<=i<=j<=n},维护一个max值即可。
    其中枚举上下界的时间复杂度为O(n^2),求区间和的复杂度为O(n),所以总时间复杂度为O(n^3)。

    for ( int i = 1 ; i <= n ; i++ )
         for ( int j = i ; j <= n ; j++ )
             ans = max(ans,accumulate(a+i,a+j+1,0));


    ②其实就是第一种方法的优化。
    这里有个很容易想到的优化,即预处理出前缀和sum[i]=a[0]+a[1]+...+a[i-1]+a[i],算区间和的时候即可将求区间和的复杂度降到O(1),枚举上下界的复杂度不变,所以总时间复杂度为O(n^2)。

     

    for ( int i = 1 ; i <= n ; i++ )
         sum[i]=sum[i-1]+a[i];
     for ( int i = 1 ; i <= n ; i++ )
         for ( int j = i ; j <= n ; j++ )
             ans = max(ans,sum[j]-sum[i-1]);


    ③可以利用动态规划的思维来继续优化,得到一个线性的算法,也是最大连续区间和的标准算法
    定义maxn[i]为以i为结尾的最大连续和,则很容易找到递推关系:maxn[i]=max{0,maxn[i-1]}+a[i]。
    所以只需要扫描一遍即可,总时间复杂度为O(n)。

    for ( int i = 1 ; i <= n ; i++ )
     {
         last = max(0,last)+a[i];
         ans = max(ans,last);
     }


    ④同样用到类似的思维。
    首先也需要预处理出前缀和sum[i],可以推出ans=max{sum[i]-min{sum[j] } | 0<=j<i<=n }。
    而最小前缀和可以动态维护,所以总时间复杂度为O(n)。

    for ( int i = 1 ; i <= n ; i++ )
         sum[i]=sum[i-1]+a[i];
     for ( int i = 1 ; i <= n ; i++ )
     {
         ans = max(ans,sum[i]-minn);
         minn = min(minn,sum[i]);
     }


    总结:虽然朴素的O(n^3)和前缀和优化的O(n^2)算法很容易想到,但代码实现却反而比方法三麻烦,第四个方法虽然有和方法三相同的复杂度,但需要一个预处理和多出的O(n)的空间,所以,方法三很好很强大。

     

    转载于:https://www.cnblogs.com/yfs123456/p/5741832.html

    展开全文
  • 最大连续区间也是线段树比较套路的做法 维护三个标记 ls,rs,ms 分别表示从当前区间左端点开始的最长连续区间,最长连续区间,右端点开始的最长连续区间 标记主要在push_up中体现 void push_up(int id,int l,int r)...

    HDU 1540 Tunnel Warfare
    HDU 4553 约会安排

    最大连续区间也是线段树比较套路的做法
    维护三个标记
    ls,rs,ms
    分别表示从当前区间左端点开始的最长连续区间,最长连续区间,右端点开始的最长连续区间
    标记主要在push_up中体现

    void push_up(int id,int l,int r)
    {
        tree[id].ml = max(max(tree[id<<1].ml,tree[id<<1|1].ml),tree[id<<1].rl+tree[id<<1|1].ll);
        tree[id].ll = tree[id<<1].ll;
        if(tree[id<<1].ll == (r+l)/2-l+1) tree[id].ll += tree[id<<1|1].ll;
        tree[id].rl = tree[id<<1|1].rl;
        if(tree[id<<1|1].rl == r-(r+l)/2) tree[id].rl += tree[id<<1].rl;
    }
    

    用左右儿子的三个标记更新父节点的三个标记
    首先是ms,显然父节点的ms等于左儿子的ms和右儿子的ms以及左儿子的rs+右儿子的ls这三者的最大值
    然后是ls,先把左二子的ls赋给他,再看左二子的ls是否与他的总区间相等,如果相等则再加上右儿子的ls。本质是看左右区间是否连通。
    rs同理

    HDU 1540 Tunnel Warfare
    最大连续区间的裸题

    //虽然对线段树的本质有点理解
    //但是线段树是个很灵活的数据结构
    //进阶一点的就是线段树应该存储什么数据
    
    //如果要维护最大连续区间
    //由于二叉树的性质  最大连续区间 的维护离不开 左端最大连续区间 和 右端最大连续区间
    
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<stack>
    using namespace std;
    
    const int maxn = 5e4+5;
    int n,m;
    struct node
    {
        int ll,rl,ml;
    }tree[maxn<<2];
    
    void push_up(int id,int l,int r)
    {
        tree[id].ml = max(max(tree[id<<1].ml,tree[id<<1|1].ml),tree[id<<1].rl+tree[id<<1|1].ll);
        tree[id].ll = tree[id<<1].ll;
        if(tree[id<<1].ll == (r+l)/2-l+1) tree[id].ll += tree[id<<1|1].ll;
        tree[id].rl = tree[id<<1|1].rl;
        if(tree[id<<1|1].rl == r-(r+l)/2) tree[id].rl += tree[id<<1].rl;
    }
    void build(int id,int l,int r)
    {
        tree[id].ll = tree[id].rl = tree[id].ml = r-l+1;
        if(l==r) return ;
        int mid = (l+r)>>1;
        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);
    }
    void update(int id,int stl,int str,int x,int c)
    {
        if(stl==str)
        {
            tree[id].ll = tree[id].rl = tree[id].ml = c;
            return ;
        }
        int mid = (stl+str)>>1;
        if(x<=mid) update(id<<1,stl,mid,x,c);
        else update(id<<1|1,mid+1,str,x,c);
        push_up(id,stl,str);
    }
    int query(int id,int stl,int str,int x)
    {
        if(stl==str || tree[id].ml==str-stl+1 || tree[id].ml==0) return tree[id].ml;
        int mid = (stl+str)>>1;
        if(x<mid+1 - tree[id<<1].rl) return query(id<<1,stl,mid,x);
        if(x>mid + tree[id<<1|1].ll) return query(id<<1|1,mid+1,str,x);
        return tree[id<<1].rl + tree[id<<1|1].ll;
    }
    int main()
    {
        int x;
        char cmd[5];
        while(~scanf("%d%d",&n,&m))
        {
            stack<int> st;
            build(1,1,n);
            while(m--)
            {
                scanf("%s",cmd);
                if(cmd[0]=='D')
                {
                    scanf("%d",&x);
                    st.push(x);
                    update(1,1,n,x,0);
                }
                else if(cmd[0]=='R')
                {
                    update(1,1,n,st.top(),1);
                    st.pop();
                }
                else
                {
                    scanf("%d",&x);
                    printf("%d\n",query(1,1,n,x));
                }
            }
        }
        return 0;
    }
    
    

    HDU 4553 约会安排
    比较复杂,维护两种最大连续区间,并且有优先级
    nls,nms,nrs分别表示女神可用的最大连续区间
    dls,dms,drs分别表示屌丝可用的最大连续区间

    查询的时候查询最大可用连续区间长度大于k的左端点

    //复杂的线段树要十分细心才行。。。
    //不然bug能调一个小时
    
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    
    const int maxn = 1e5+5;
    int n,q;
    struct node
    {
        int l,r;
        int dls,drs,dms;
        int nls,nrs,nms;
        inline int len()
        {
            return r-l+1;
        }
    }tree[maxn<<2];
    void build(int id,int l,int r)
    {
        tree[id].l = l,tree[id].r = r;
        tree[id].dls = tree[id].drs = tree[id].dms = tree[id].len();
        tree[id].nls = tree[id].nrs = tree[id].nms = tree[id].len();
        if(l==r) return ;
        int mid = (l+r)>>1;
        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);
    }
    void push_up(int id)
    {
        tree[id].dms = max(max(tree[id<<1].dms,tree[id<<1|1].dms),tree[id<<1].drs+tree[id<<1|1].dls);
        tree[id].dls = tree[id<<1].dls;
        if(tree[id<<1].dls==tree[id<<1].len()) tree[id].dls+=tree[id<<1|1].dls;
        tree[id].drs = tree[id<<1|1].drs;
        if(tree[id<<1|1].drs==tree[id<<1|1].len()) tree[id].drs+=tree[id<<1].drs;
    
        tree[id].nms = max(max(tree[id<<1].nms,tree[id<<1|1].nms),tree[id<<1].nrs+tree[id<<1|1].nls);
        tree[id].nls = tree[id<<1].nls;
        if(tree[id<<1].nls==tree[id<<1].len()) tree[id].nls+=tree[id<<1|1].nls;
        tree[id].nrs = tree[id<<1|1].nrs;
        if(tree[id<<1|1].nrs==tree[id<<1|1].len()) tree[id].nrs+=tree[id<<1].nrs;
    }
    void push_down(int id)
    {
        int lson=id<<1,rson=id<<1|1;
        if(tree[id].dms==tree[id].len())
        {
            tree[lson].dls=tree[lson].dms=tree[lson].drs=tree[lson].len();
            tree[rson].dls=tree[rson].dms=tree[rson].drs=tree[rson].len();
        }
        else if(tree[id].dms==0)
        {
            tree[lson].dls=tree[lson].dms=tree[lson].drs=0;
            tree[rson].dls=tree[rson].dms=tree[rson].drs=0;
        }
        if(tree[id].nms==tree[id].len())
        {
            tree[lson].nls=tree[lson].nms=tree[lson].nrs=tree[lson].len();
            tree[rson].nls=tree[rson].nms=tree[rson].nrs=tree[rson].len();
        }
        else if(tree[id].nms==0)
        {
            tree[lson].nls=tree[lson].nms=tree[lson].nrs=0;
            tree[rson].nls=tree[rson].nms=tree[rson].nrs=0;
        }
    }
    void update(int id,int l,int r,int op)
    {
        //printf("%d %d %d %d\n",tree[id].l,tree[id].r,l,r);
        if(tree[id].l==l && tree[id].r==r)
        {
            if(op==1)
            {
                tree[id].dls=tree[id].drs=tree[id].dms=0;
                tree[id].nls=tree[id].nrs=tree[id].nms=tree[id].len();
            }
            if(op==2)
            {
                tree[id].dls=tree[id].drs=tree[id].dms=0;
                tree[id].nls=tree[id].nrs=tree[id].nms=0;
            }
            if(op==3)
            {
                tree[id].dls=tree[id].drs=tree[id].dms=tree[id].len();
                tree[id].nls=tree[id].nrs=tree[id].nms=tree[id].len();
            }
            return ;
        }
        push_down(id);
        int mid = (tree[id].l+tree[id].r)>>1;
        if(r<=mid) update(id<<1,l,r,op);
        else if (l>mid) update(id<<1|1,l,r,op);
        else
        {
            update(id<<1,l,mid,op);
            update(id<<1|1,mid+1,r,op);
        }
        push_up(id);
    }
    int query(int id,int x,int op)
    {
        if(tree[id].l==tree[id].r) return tree[id].l;
        push_down(id);
        if(op==1)
        {
            if(tree[id].dls>=x) return tree[id].l;
            if(tree[id<<1].dms>=x) return query(id<<1,x,op);
            if(tree[id<<1].drs+tree[id<<1|1].dls>=x) return tree[id<<1].r-tree[id<<1].drs+1;
            return query(id<<1|1,x,op);
        }
        if(op==2)
        {
            if(tree[id].nls>=x) return tree[id].l;
            if(tree[id<<1].nms>=x) return query(id<<1,x,op);
            if(tree[id<<1].nrs+tree[id<<1|1].nls>=x) return tree[id<<1].r-tree[id<<1].nrs+1;
            return query(id<<1|1,x,op);
        }
    }
    int main()
    {
        int t;
        int kase=0;
        char cmd[10];
        int x,l,r;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&q);
            build(1,1,n);
            printf("Case %d:\n",++kase);
            while(q--)
            {
                scanf("%s",cmd);
                if(cmd[0]=='S')
                {
                    scanf("%d%d",&l,&r);
                    update(1,l,r,3);
                    printf("I am the hope of chinese chengxuyuan!!\n");
                }
                else if (cmd[0]=='D')
                {
                    scanf("%d",&x);
                    if(tree[1].dms>=x)
                    {
                        int k = query(1,x,1);
                        printf("%d,let's fly\n",k);
                        update(1,k,k+x-1,1);
                    }
                    else printf("fly with yourself\n");
                }
                else
                {
                    scanf("%d",&x);
                    if(tree[1].dms>=x)
                    {
                        int k = query(1,x,1);
                        printf("%d,don't put my gezi\n",k);
                        update(1,k,k+x-1,2);
                    }
                    else if (tree[1].nms>=x)
                    {
                        int k = query(1,x,2);
                        printf("%d,don't put my gezi\n",k);
                        update(1,k,k+x-1,2);
                    }
                    else printf("wait for me\n");
                }
            }
        }
        return 0;
    }
    
    
    展开全文
  • Q:查询该点所在的最大连续区间长度; R:把最近一次删除的点还原;   我一开始的思路是:对于最长连续区间长度的查询,用的是set来存储之前被删除的点(目的是让点排好序),用数组模拟一下栈按删除顺序存点,...
  • 最大连续区间和算法详解+代码

    千次阅读 2018-06-07 14:06:58
    本篇主要记录了最大连续区间和的暴力算法和dp算法(三种写法) 以及讲解了求最大区间和的区间左右下标的方法 ----------------------------------------------------------------------------------- 问题概述 ...
  • 题意 有n个连在一起的地道 接下来有m个操作 D x 炸掉x号地道 炸掉后x所在的区间就不连续了 Q x 查询输出包括x的最大连续区间长度 R修复最后一个被炸的地道 注意输入R时可能并没有需要修复的地道 线段树的区间...
  • D x 表示去掉第x点,Q x表示需输出含 x 的最大连续区间的长度,R x表示还原最后去掉的点 解析: 看到区间查询和修改很明显是线段树 #include<iostream> #include<string> #include<stack&g...
  • 题意 :一段区间 操作1 切断点 操作2 恢复最近切断的一个点 操作3 单点查询该点所在最大连续区间 思路: 主要是push_up : 设区间x 为母区间 x<<1 ,x<<1|1分别为两个子区间 x的左端连续子段和 :当x&...
  • D x 表示去掉第x点,Q x表示需输出含 x 的最大连续区间的长度,R x表示还原最后去掉的点 思路: 第一种思路:利用线段树求解, 线段树维护一个最长连续子段和,然后查询的时候判断x点是在左边区间还是右边区间,如果...
  • 所以自然而然的想到利用栈来解决,在本题中使用数组来模拟栈操作,其次,Q代表查询包含第i个地道的最大连续地道数目,这个就表示要求求出包含在本节点在内的最大连续区间的和。在下面解题中,1表示地道未被炸毁,0...
  • 最大连续区间和的几种方法

    千次阅读 2015-07-11 21:00:54
    今天做bestcoder想到的,几种做最大连续区间和的方法。 定义最大连续区间和:给定一个长度为n的序列a[1],a[2]...a[n],求一个连续的子序列a[i],a[i+1]...a[j-1],a[j]使得a[i]+a[i+1]...+a[j-1]+a[j]最大。 ...
  • D x 表示去掉第x点,Q x表示需输出含 x 的最大连续区间的长度,R x表示还原最后去掉的点 解析 思路很简单,首先,存在的点标1,不存在的标0 对于去掉点非常自然地拿stack存一下 然后线段树应当记录各种最大连续...
  • 题目:有一个数组,求他的最大(最长)连续区间(数字是连续的区间)。 我的解法,如下: class Finder(object): ''' 判断两个相邻的数字是否连续,若连续: 1.继续向后判断 2.记录连续长度 最后返回...
  • Problem A: 最大连续区间和 Time Limit: 1 Sec Memory Limit: 32 MB Submit: 43 Solved: 2 [Submit][Status] Description 你的任务是找出一串数字中,哪一些连续数字之和最大,并输出这个和。 例如:输入...
  • 最大连续区间和是一个经典的问题。给定一个长度为n的序列a[1],a[2]...a[n-1],a[n],求一个连续的子序列a[i],a[i+1]...a[j-1],a[j],使得a[i]+a[i+1]...a[j-1]+a[j]最大。①最简单最容易想到的就是根据定义来枚举。...
  • 题目背景 小新经常陪小白去公园玩,也就是所谓的...小新为了省事,每次遛狗的时候都会事先规定一个范围,小白只可以选择第aa个和第bb个公园之间(包括aa、bb两个公园)选择连续的一些公园玩。小白当然希望选出的公...
  • 今天正好做到一道有关"最大子矩阵问题"的题目,看到这篇文章不错,顺便转载过来。...最大连续区间和是一个经典的问题。给定一个长度为n的序列a[1],a[2]...a[n-1],a[n],求一个连续的子序列a[i],a[i+1]...a[j-1],a
  • 因为正要学 动态最大连续区间和 所以先用分治做一下静态的。。。 以前是dp做的o(n) 分治大约是是nlogn 分治: #include #include #include #include #include #include #include #include #...
  • 1.输出数组最大连续区间的和 动态规划: 设f(i) 为长度i的最大连续区间的和。 则有 f(i) = f(i-1) +a(i) 如果f(i-1)>0 f(i) = a(i) 如果f(i-1)<0 依次从小大求解f(i)的最大值 int nCurSum = 0; int ...
  • 连续区间为公差为1的等差数列。 输入: [1, 2, 99, 3, 4, 5, 6, 5, 4, 4, 2, 6, 3, 1, 8, 5, 3, 6, 1, 2, 3, 2, 3, 4, 5, 6] 输出: [2, 3, 4, 5, 6] def get_continue_seq(str_list): ls = eval(str_list) ...
  • /************************************** 题目大意: 一条直线上的有n个顶点;...线段树,求最大连续区间,操作类似于pku3667; ls 记录区间左端点开始的最大连续个数, rs 记录区间右端点开始的最大的连续个
  • 最大连续区间和的水题 #include #include #include #include #include #include #include using std::min; using std::max; long getint() { long rs=0;bool sgn=-1;char tmp; do tmp=getchar(); ...
  • 求一个数组中,一段连续区间最大和。 dp(i+1)=max(num[i+1], num[i+1]+dp(i)); dpi表示以第i元素结尾的最大区间和。 #include<iostream> using namespace std; int main() { int n; cin>>n; int* a...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,256
精华内容 1,302
关键字:

最大连续区间