백준 2104, 6549 C++ 풀이

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

 

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

 

2104 부분배열 고르기

구간의 최솟값*구간합을 최대로 만들어야 한다.

A[i]를 전체 구간의 최솟값이라고 했을 때, 

A[i]를 포함하여 최대값을 만들려면 A[i]*전체구간합이 최대값인 것은 자명하다.

다른 최대값을 확인하려면 A[i]을 제외한 다른 구간을 봐야만 한다.

(~A[i-1]) , (A[i+1]~) 이 두 구간으로 자를 수 있다.

이를 반복하면 최대값을 얻을 수 있다.

 

 

#include <bits/stdc++.h>
#define ll long long
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;


ll ans = 0;
ll arr[1000001];

//비재귀 세그먼트 트리
int tree_size, base;
vector<pair<ll,ll> > seg_tree;

void init(int size) {
    tree_size = size;
    seg_tree.resize(tree_size << 2, {0x7f7f7f7f, 0});
    for (base = 1; base < tree_size; base <<= 1);
}

void update(int i, ll x) {
    i += base;
    seg_tree[i] = {x, i - base};
    for (i = i >> 1; i > 0; i = i >> 1)
        seg_tree[i] = min(seg_tree[i << 1], seg_tree[i << 1 | 1]);
}

pair<ll,ll> query(int p, int q) {
    // [p,q]
    p += base, q += base;

    pair<ll,ll> ret = {0x7f7f7f7f, 0};
    while (p < q) {
        if (p & 1) ret = min(ret, seg_tree[p++]);
        if (~q & 1) ret = min(ret, seg_tree[q--]);

        p = p >> 1, q = q >> 1;
    }

    if (p == q) ret = min(ret, seg_tree[p]);
    return ret;
}

void f(int s, int e) {
    if (s >= e)
        return;
    ll MIN;
    int idx;
    tie(MIN, idx) = query(s, e);
    ans = max(ans, MIN * (arr[e + 1] - arr[s]));
    f(s, idx - 1);
    f(idx + 1, e);
}

int main() {
    fastio;
    int N, tmp;
    cin >> N;
    init(N);
    for (int i = 0; i < N; i++) {
        cin >> tmp;
        arr[i + 1] = arr[i] + tmp;
        ans = max(ans, 1ll * tmp * tmp);
        update(i, tmp);
    }
    f(0, N - 1);
    cout << ans;
    return 0;
}

 

 

 

6549 히스토그램에서 가장 큰 직사각형

직사각형의 넓이는 가로*높이이다.

구간의 길이를 가로라고 했을 때, 높이는 구간의 최솟값이다.

A[i]를 전체 구간의 가장 작은 높이라고 했을 때, 

A[i]를 포함하여 최대값을 만들려면 A[i]*전체 가로 길이가 최대값인 것은 자명하다.

다른 최대값을 확인하려면 A[i]을 제외한 다른 구간을 봐야만 한다.

(~A[i-1]) , (A[i+1]~) 이 두 구간으로 자를 수 있다.

이를 반복하면 최대값을 얻을 수 있다.

 

#include <bits/stdc++.h>
#define ll long long
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
#define X first
#define Y second

ll ans;

//비재귀 세그먼트 트리
int n, base;
vector<pair<int, int> > tree;

void init(int size) {
    n = size;
    tree.resize(n << 2, {0x3f3f3f3f, -1});
    for (base = 1; base < n; base <<= 1);
}

void update(int i, int x) {
    i += base;
    tree[i].X = x;
    tree[i].Y = i - base;
    for (i = i >> 1; i > 0; i = i >> 1)
        tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
}

pair<int, int> query(int p, int q) {
    p += base, q += base;

    pair<int, int> ret = {0x7f7f7f7f, -1};
    while (p < q) {
        if (p & 1) ret = min(ret, tree[p++]);
        if (~q & 1) ret = min(ret, tree[q--]);

        p = p >> 1, q = q >> 1;
    }

    if (p == q) ret = min(ret, tree[p]);
    return ret;
}

void f(int s, int e) {
    int MIN, mid;
    if (s >= e)
        return;
    tie(MIN, mid) = query(s, e);
    ans = max(ans, 1ll * MIN * (e - s + 1));
    f(s, mid - 1);
    f(mid + 1, e);
}

int main() {
    fastio;
    int N, tmp;
    cin >> N;
    while (N != 0) {
        ans = 0;
        init(N);
        for (int i = 0; i < N; i++) {
            cin >> tmp;
            ans = max(ans, 1ll * tmp);
            update(i, tmp);
        }
        f(0, N - 1);
        cout << ans << "\n";
        cin >> N;
    }
    return 0;
}