넣은 날짜를 j, 꺼낸 날짜를 i라 하자.

김치의 맛은 $(i-j)\times T[i] + V[j]$이고, $T[i] \geq T[i+1]$이다.

이때, $i-j\leq D$이어야 한다.

대충 제한을 보면 N개의 i or j값에 대해 최적인 j or i 값을 logN에 구해야 함

DnC Opt를 쓰는 문제임은 웰논

$D(t,i)=\min_{1\leq j \leq n}D(t-1, j)+C(j,i)$ 꼴로 문제를 바꿀 수 있나?

O((t범위)NlogN)인데 제한이 다 10만이라 믛

j에 대해 $(i-j)\times T[i]$를 최소화시키는 i를 구하는 문제?

$i\times T[i] - j\times T[i]$

D(2, j)를 넣을 때 기준 최대맛, D(1, i)를 $i\times T[i]$, C(j, i)를 $-j\times T[i]$ 라고 하면

$D(2, j)=\min D(1, i) + C(j, i)$

이때 최적인 i가 j가 증가할 때 단조증가하는가?

j에 대한 최적인 i에서

i-1과 j+1을 생각해보면

$(i-j)\times T[i] \geq (i-j-1)\times T[i-1]$였던 거니까

$(i-j-1)\times T[i] \geq (i-j-1)\times T[i-1]-T[i]\geq(i-j-2)\times T[i-1]$이므로

$(i-(j+1))\times T[i] \geq (i-1-(j+1))\times T[i-1]$임

즉, i-1은 고려할 필요가 없음

i-k (k>0) 에 대해서도 마찬가지.

따라서 최적인 i는 j가 증가할 때 단조증가하고, Dnc Opt를 쓸 수 있다.