# [Platinum II] Apteka [문제 링크](https://www.acmicpc.net/problem/8571) ## 문제 설명 <p>Jaś stoi ostatni w kolejce do apteki. Ponieważ Jasiowi bardzo się śpieszy, to postanowił, że spróbuje się pozamieniać miejscami z niektórymi osobami, nawet jeśli musiałby za to zapłacić.</p> <p>Każda osoba jest chętna do zamiany, ale $i$-tej osobie za przesunięcie o każde jedno miejsce dalej w kolejce trzeba zapłacić $c_i$. Dokładniej, jeśli Jaś jest $k$ miejsc ($k > 0$) dalej od kasy niż pewna osoba i jeśli chce się z nią zamienić miejscami, to musi jej zapłacić kwotę $k \cdot c_i$.</p> <p>Jaś chciałby być pierwszy w kolejce i zastanawia się, jak dokonywać zamian, aby wydać jak najmniej.</p> ## 입력 <p>Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą $n$ ($1 ≤ n ≤ 10^6$), oznaczającą liczbę osób, które stoją przed Jasiem w kolejce do apteki.</p> <p>Następny wiersz wejścia zawiera $n$ liczb całkowitych $c_1, c_2, \dots , c_n$ ($1 ≤ c_i ≤ 10^9$), gdzie $c_i$ oznacza kwotę, jaką Jaś musi zapłacić $i$-tej osobie za przesunięcie o każde miejsce dalej w kolejce. Kolejność osób liczona jest od osoby, za którą bezpośrednio stoi Jaś, a więc od końca kolejki do jej początku.</p> ## 출력 <p>Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą minimalnej kwocie, jaką Jaś musi zapłacić, aby być pierwszym w kolejce.</p> ## 풀이 dp[i]를 i까지 움직일 때의 최소 cost로 두면, $dp[i] = min(dp[j]+(i-j)c_i)$고 $A_i$를 x로 두면 기울기가 -j라 단조 감소하여 CHT가 가능하다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAX = 1'000'001; ll c[MAX], dp[MAX]; struct element { ll a, b; double x=-1e150; }; double meetX(element a, element b) { return (double)(a.b-b.b)/(b.a-a.a); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=1;i<=n;i++) cin >> c[i]; vector<element> stk; for(int i=1;i<=n;i++) { ll x = c[i]; element cur = {-(i-1), dp[i-1]}; while(!stk.empty()) { cur.x = meetX(cur, stk.back()); if(cur.x>stk.back().x) break; stk.pop_back(); } stk.push_back(cur); int left=0, right=stk.size()-1; while(left<right) { int mid = left+right+1>>1; if(x<stk[mid].x) right = mid-1; else left = mid; } dp[i] = stk[left].a*x+stk[left].b + i*c[i]; } cout << dp[n]; } ```