[백준] 12846 - 무서운 아르바이트 (c++)

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

 

문제 요약

성화의 편의점에서는 최저 일급 기준으로 급여를 지급하며, 연속으로 일해야 한다.
준수는 n일 동안 최대 이익을 얻을 수 있도록 일해야 한다.
최대 수익을 계산하라.

 

풀이 (NlogN)

• 분할 정복
• 세그먼트 트리

일급을 히스토그램으로 표현해 보면 가장 큰 직사각형 문제랑 같아진다는 걸 알 수 있다.

전체 구간을 시작으로 구간에서 가장 낮은 막대를 기준으로 분할정복할 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mid (st+en>>1)

int n;
vector<ll> hei;

vector<int> seg(1e6);
int init(int i,int st,int en) {
    if(st==en)
        return seg[i]=st;
    int a=init(i*2,st,mid),b=init(i*2+1,mid+1,en);
    return seg[i]=(hei[a]<hei[b])?a:b;
}
int query(int i,int st,int en,int l,int r) {
    if(en<l||st>r)
        return 0;
    if(st>=l&&en<=r)
        return seg[i];
    int a=query(i*2,st,mid,l,r),b=query(i*2+1,mid+1,en,l,r);
    return (hei[a]<hei[b])?a:b;
}

ll dc(int st,int en) {
    if(st>en)
        return 0;
    int mni=query(1,1,n,st,en);
    ll cc = hei[mni]*(en-st+1);
    ll mx=max(dc(st,mni-1),dc(mni+1,en));
    return max(cc,mx);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin>>n;
    hei.resize(n);
    for(auto&x:hei)cin>>x;
    hei.insert(hei.begin(),1e9);

    init(1,1,n);
    cout<<dc(1,n);
}