https://codeforces.com/contest/1313/problem/C2
<문제설명>
skyscraper 최대 5e5개 세우려고 한다. 각 건물마다 최대 높이 한도가 주어진다.
그 어떤 건물도 그 건물 기준으로 왼편, 오른편에 더 높은 건물이 둘 다 존재하지 않도록 건물을 올리려고 한다.
(전체적인 모양 : non-descending - nod-increasing)
높이의 합이 최대일 때 건물들의 높이를 모두 출력하라
<풀이>
a[i] : 입력값. 건물의 최대 높이 한도
f[i] : 1번~i번까지 건물을 올리는데, i번 건물을 최대 높이로 하는 건물들의 높이 합.
g[i] : n번~i번까지(거꾸로) 건물을 올리는데, i번 건물을 최대 높이로 하는 건물들의 높이 합.
f[i]+g[i] - a[i]가 최대인 i를 가장 높은 건물로 취급하면 된다.
f[i]를 어떻게 구하는지?
l[i] : i왼편으로 a[i]보다 작거나 같은 높이를 갖는 인덱스 중 가장 가까운 인덱스 (nsv: https://suuntree.tistory.com/139)
f[0] = 0
if(a[i]>a[i-1]) f[i] = f[i-1]+a[i];
else f[i] = f[l[i]] + (i-l[i])*a[i];
g[i]도 비슷한 방법으로 구해준다.
<코드>
ll n, a[MAX], l[MAX], r[MAX], f[MAX], g[MAX];
int main() {
FAST; cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
stack<int> stk;
stk.push(0);
for (int i = 1; i <= n; i++) {
while (a[stk.top()] > a[i]) stk.pop();
l[i] = stk.top();
stk.push(i);
}
while (!stk.empty()) stk.pop();
stk.push(n + 1);
for (int i = n; i >= 1; i--) {
while (a[stk.top()] > a[i]) stk.pop();
r[i] = stk.top();
stk.push(i);
}
for (int i = 1; i <= n; i++) {
if (a[i] >= a[i - 1]) f[i] = f[i - 1] + a[i];
else f[i] = f[l[i]] + (i - l[i]) * a[i];
}
for (int i = n; i >= 1; i--) {
if (a[i] >= a[i + 1]) g[i] = g[i + 1] + a[i];
else g[i] = g[r[i]] + (r[i] - i) * a[i];
}
ll mx = 0, idx=0;
for(int i=1;i<=n;i++)
if (mx < f[i] + g[i] - a[i]) {
mx = f[i] + g[i] - a[i];
idx = i;
}
for (int i = idx - 1; i >= 1; i--)
if (r[i] <= idx) a[i] = a[r[i]];
for (int i = idx + 1; i <= n; i++)
if (l[i] >= idx) a[i] = a[l[i]];
for (int i = 1; i <= n; i++)
cout << a[i] << " \n"[i == n];
}
<생각>
nsv는 이런 히스토그램? 문제에 써먹을 일이 많을 것으로 보인다