AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 126. 最大的和(扫描线O(n|S|log(n))    原题链接    简单

作者: 作者的头像   这个显卡不太冷 ,  2019-08-13 19:25:07 ,  阅读 704


1


1

题目联动:2019HDU多校-HDU6638 Snowy Smile

提供一种扫描线做法,复杂度为$O(nSlog(n))$其中S表示的是非零点的个数。

考虑按照x排序。然后枚举x作为子矩阵的左边界,依次加入后面的点作为子矩阵的由边界。

对于每个x相同的点,在线段树上维护一个长度为y的区间连续最大和(ACwing245)。把每个x相同的点加入线段树。最后求一次区间连续最大和。

也就是枚举左右边界,利用区间连续最大和“求取”上下边界。

当坐标很分散但点不多的时候,例如2000个坐标,$n^3$的DP做法将不再有效。离散化以后的扫描线做法优势将会非常明显。

但对于本题来说。由于坐标非常集中,而且当n=100的时候点数接近10000个。这个做法将退化为$O(n^3log(n))$,不如DP做法。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 * 100 + 233;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define max(a, b) (a) > (b) ? (a) : (b)
struct Node{
    int l, r, lsum, rsum, sum, dat;
}t[maxn * 4];
void build(int p, int l, int r)
{
    t[p].l = l; t[p].r = r;
    if(l == r) {t[p].lsum = 0, t[p].rsum = 0, t[p].sum = 0, t[p].dat = 0; return;}
    int mid = (l + r) >> 1;
    build(ls(p), l, mid); build(rs(p), mid + 1, r);
    t[p].dat = t[p].rsum = t[p].lsum = t[p].sum = 0;
}
void update(int p, int l, int r, int v)
{
    if(l <= t[p].l && r >= t[p].r)
    {
        t[p].dat += v;
        t[p].lsum += v;
        t[p].rsum += v;
        t[p].sum += v;
        return ;
    }
    int mid = (t[p].l + t[p].r) >> 1;
    if(l <= mid) update(ls(p), l, r, v);
    if(r > mid) update(rs(p), l, r, v);
    t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
    t[p].lsum = max(t[ls(p)].lsum, t[ls(p)].sum + t[rs(p)].lsum);
    t[p].rsum = max(t[rs(p)].rsum, t[rs(p)].sum + t[ls(p)].rsum);
    t[p].dat = max(max(t[ls(p)].dat, t[rs(p)].dat), t[ls(p)].rsum + t[rs(p)].lsum);
}
int ask()
{
    return t[1].dat;
}
int a[101][101];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    int ans = INT_MIN;
    for(int i = 1; i <= n; i++)
    {
        build(1, 1, n);
        for(int k = i; k <= n; k++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(a[j][k])
                {
                    update(1, j, j, a[j][k]);
                }
            }
            ans = max(ans, ask());
        }
    }
    cout << ans << endl;
}

3 评论


用户头像
whsstory   2019-11-08 10:00     回复

唔,经典的线段树维护分治欸,好,好!


用户头像
hohn1161   2019-10-20 13:34     回复

%%%


用户头像
cbio   2019-09-10 15:33     回复

%%%

你确定删除吗?

© 2018-2020 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息