BOJ 18251 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

https://www.acmicpc.net/problem/18251

18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

 

 

노드의 개수와 각각의 노드의 가중치를 입력받고 포화이진트리 모양을 만들었을 때 직사각형 영역을 그려서 영역 내에 있는 가중치들의 합을 최대로 만드는 문제이다.

 

 

만약 노드들의 좌표가 주어져 있다면  문제처럼 해결할 수 있을 것이다.

 

 

따라서 우리는 노드들의 좌표를 정해줄 것이다.

 

 

노드들의 $x$좌표는 트리를 전위 순회하는 순서로 정할 수 있다. 전위 순회하여 가장 먼저 방문하는 노드의 $x$좌표를 1, 그다음 노드를 $2$, ...... 마지막 노드를 $n$으로 정하면 된다.

 

 

노드들의 y좌표는 트리에서의 높이로 정할 수 있다. 그러면 $y$좌표의 최댓값은 $\log_{2}{N}$이다.

 

 

중위 순회 순서이다.

 

 

이제 노드들의 좌표를 정해주었으므로 스위핑을 통해 해결할 수 있다.

 

 

$y$좌표의 최댓값이 약 $20$ 정도이므로 BOJ 10167 금광 풀이에서 소개한 $O(N^{3})$ dp 방식으로도 해결이 가능하다.

 

 

 

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int N;
ll W[262144];

struct Point{
    int x, y;
    ll w;
};

int cnt=1;
vector<Point> p;

void pre_order(int x, int y)
{
    if(x*2<=N){ pre_order(x*2, y-1); }
    p.push_back({cnt, y, W[x]});
    cnt++;
    if(x*2+1<=N){ pre_order(x*2+1, y-1); }
}

int getlog2(int a)
{
    int ret=0;
    while(a){ a>>=1; ret++; }
    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N;
    int H=getlog2(N);
    ll sum=0, mx=-9999999999;
    for(int i=1; i<=N; i++){
        cin >> W[i];
        sum+=W[i];
        mx=max(mx, W[i]);
    }
    if(mx<0){ cout << mx << "\n"; return 0; }
    pre_order(1, H);
    ll ans=0;
    for(int y1=1; y1<=H; y1++){
        for(int y2=y1; y2<=H; y2++){
            ll S=0;
            for(int i=0; i<N; i++){
                if(p[i].y<y1 || y2<p[i].y){ continue; }
                S=max(S+p[i].w, 0LL);
                ans=max(ans, S);
            }
        }
    }
    cout << ans << "\n";
    return 0;
}