BOJ 21337 - Atomic Energy
대략 어느정도까지 DP를 $O(n'^2)$ 로 크게 모두 계산해준다
$a_k = \text{Min}{1 \le i \le k-1} a_i+a{k-i}$ 이다.
이후에 $k$에 대해 생각해보자.
$k=x+y$ 이고 $a_k$ 를 가장 작게 만드는 조합이 $a_x+a_y$ 라면, 항상 $x\le y$ 라 할 때, $x \le n$ 이 될 수 있다.
$n$ 개의 $a_i$에 대해서 $\dfrac{a_i}{i}$ 가 가장 작은것을 고르는게 최적이다. 이걸 $x$라 하자.
따라서 $k$ 에서 $a_x$ 로 구한 DP 전까지만 모두 써주고 나머지 값은 DP 값을 더해주면 된다.
위에서 대략 어느정도까지라고만 표현했지만 이걸 비둘기 집의 원리로 특정할 수 있다.
$x$ 개 이상의 $a_x$ 가 아닌 값들이 있다고 하자.
비둘기 집의 원리에 의해 이것들의 인덱스를 합쳐 $x$의 배수를 만들 수 있다.
$x$의 배수를 생각해보면 어떤 수가 $x$의 배수일 때 그건 모두 $a_x$ 여러개로 환원시킬 수 있고 최적해를 헤치지 않는다.
따라서 분해 과정에서 $a_x$ 으로 분해되지 않는것은 최대 $x+1$ 개이다.
Comments