백준 14180 - 배열의 특징 [Python]

www.acmicpc.net/problem/14180

14180번: 배열의 특징

배열 t에서,

\(A_{i} = t_{1} 부터 t_{i} 의 합\)

B = 배열 t의 특징 이라고 하면,

 

배열 t의 n번째 수를 옮길 떄의 최댓값을 dp[n]이라고 하면, 이 n번째 수를 옮기는 방향에 따라 두가지로 나누어 풀면 된다.

 

왼쪽으로 옮길 때는,

\(i<n\) 에서

\(dp[n] = max( (i * t_{n} - t_{i-1}) + B + A_{n-1} - n * t_{n} )\) 이고,

 

오른쪽으로 옮길 때는,

\(n<i\) 에서

\(dp[n] = max( (i * t_{n} - t_{i}) + B + A_{n} - n * t_{n} )\) 이다.

 

선분 방향 잘 보면서 적용하면 된다. 헷갈려서 뒤지는줄

 

코드에서 insert1, bs는 왼쪽 경우이고,

insert2, bs2는 오른쪽 경우이다.

MAXN = 200005
a = [0 for _ in range(MAXN)]
b = [0 for _ in range(MAXN)]
 
def getX(f, g):
    return (f[1] - g[1])/(g[0] - f[0])
 
def insert1(x):
    k.append(x)
    while len(k)>2 and getX(k[-2], k[-1]) <= getX(k[-3], k[-2]):
        k.pop(-2)
 
def insert2(x):
    k.append(x)
    while len(k)>2 and getX(k[-2], k[-1]) >= getX(k[-3], k[-2]):
        k.pop(-2)
 
def bs(x):
    lo = 0
    hi = len(k) - 2
    while lo <= hi:
        mid = (lo+hi)//2
        if getX(k[mid], k[mid+1]) < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return k[lo][0] * x + k[lo][1]
 
def bs2(x):
    lo = 0
    hi = len(k) - 2
    while lo <= hi:
        mid = (lo+hi)//2
        if getX(k[mid], k[mid+1]) > x:
            lo = mid + 1
        else:
            hi = mid - 1
    return k[lo][0] * x + k[lo][1]
 
n = int(input())
t = list(map(int, input().split()))
 
for i in range(1, n+1):
    a[i] = a[i-1] + t[i-1]
    b[i] = b[i-1] + t[i-1] * i
 
k = [(1, 0)]
ans = b[n]
for i in range(2, n+1): #1~i
    now = bs(t[i-1]) + a[i-1] - i * t[i-1] + b[n]
    ans = max(ans, now)
    insert1((i, -a[i-1]))
 
k = [(n, -a[n])]
for i in range(n-1, 0, -1):
    now = bs2(t[i-1]) + a[i] - i * t[i-1] + b[n]
    ans = max(ans, now)
    insert2((i, -a[i]))
 
print(ans)