누적합 응용 - prefix/suffix min/max 배열 이용한 테크닉
1. 문제 29726번: 숏코딩의 왕 브실이 (acmicpc.net) 29726번: 숏코딩의 왕 브실이 숏코딩의 왕 브실이는 오늘도 숏코딩을 한다. 브실이가 제출한 코드 길이가 수열 $A_1, A_2, \cdots, A_N$로 주어진다. 브실이의 행복도는 자신의 코드 길이에 대한 수열에 따라 달라지는데, 현재 수열 www.acmicpc.net 2. 풀이 $$\sum_{i = 1}^{L-1} A_{i+1} - A_{i} = A_{L} - A_{1}$$을 관찰하는 것은 어렵지 않다. 주어진 합은 배열을 알면 양쪽 끝의 두 원소만을 이용해서 구할 수 있다. 이 의미는, $A_{1}, A_{2}, A_{3}, ... , A_{N}$이 주어질때, 중간의 원소 $A_{2}, A_{3}, ... ,A_{N-1}$는 ..