想用线段树做一下,但是WA了三个点(2,9,10),大佬可以看看吗?
查看原帖
想用线段树做一下,但是WA了三个点(2,9,10),大佬可以看看吗?
302852
小丁小丁楼主2020/8/25 21:24
#include <cstdio>
#include <algorithm>
#define maxn 20010
using namespace std;

int m, n;
int a[105][maxn];
int r[maxn];

struct node{
    int lsum, rsum, ssum;
} d[maxn << 2];

int ls(int p){          //*左儿子
    return p << 1;
}

int rs(int p){          //*右儿子
    return p << 1 | 1;
}

void push_up(int p){        //*上传
    d[p].lsum = max(d[ls(p)].lsum, d[ls(p)].ssum + d[rs(p)].lsum);
    d[p].rsum = max(d[rs(p)].rsum, d[rs(p)].ssum + d[ls(p)].rsum);
    d[p].ssum = max(max(d[ls(p)].ssum, d[rs(p)].ssum), d[ls(p)].rsum + d[rs(p)].lsum);
}

void build(int s,int t,int p){      //*建树
    if(s==t){
        d[p].lsum = d[p].rsum = d[p].ssum = r[s];
        return;
    }
    int mid = (s + t) >> 1;
    build(s, mid, ls(p));
    build(mid + 1, t, rs(p));
    push_up(p);
}

int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m;i++)
        for (int j = 1; j <= n;j++)
            scanf("%d", &a[i][j]);		//*输入
    for (int j = 1; j <= n;j++){
        int temp = -200;
        for (int i = 1; i <= m;i++){
            if(a[i][j]>temp)			//*找每列最大值
                temp = a[i][j];
        }
        r[j] = temp;
    }

    build(1, n, 1);

    printf("%d", d[1].ssum);
    return 0;
}
2020/8/25 21:24
加载中...