문제이 문제는 BarkingDog 님의 블로그를 참고했습니다. N개의 정점을 가진 트리에 대해 색깔의 개수가 bound되어 있다고 가정하고 계산해 봅시다. 먼저 다음과 같이 수열을 정의합시다.$S_k$ : k개의 색깔로 최소 비용을 만들수 있는 트리의 정점 개수의 최솟값 수열을 이렇게 정의하는 이유는 다음과 같습니다.$S_k=n$이면 1~n개의 정점을 가진 트리는 색깔을 $k$개 이하만 사용해서 최솟값을 만들 수 있습니다.즉, 우리는 $S_k \geqslant 100,000$ 인 $k$를 찾으면 됩니다. 이제 k개의 색깔로 최소 비용을 만들수 있고, 정점 개수가 최소인 트리에 대해 생각해 봅시다.색깔이 k인 정점이 항상 존재하므로 root를 색깔이 k인 임의의 정점으로 정합시다.root의 색깔이 k이기 ..

문제 문제에서 다음의 조건중 하나가 성립하면 i번 퀘스트를 깰수 있었다.1. STR $\leqslant$ STR[i] 2. INT $\leqslant$ INT [i]  게임 중간의 어떤 상태에 대해 생각해보자.조건 1에 의해 가장 마지막으로 깬 게임을 i번 게임, 조건 2에 의해 가장 마지막으로 깬 게임을 j번 게임이라고 하면, $\text{STR[k]} \leqslant \text{STR}[i]$ 인 k번 게임들과 $\text{ INT [k]} \leqslant \text{INT}[i]$ 인 k번 게임들은 모두 깨져 있거나 깰 수 있다. STR에 의해 정렬된 퀘스트 배열 a와 INT에 의해 정렬된 퀘스트 배열 b가 있다고 하자. 우리가 방금 한 관찰에 따르면 게임을 플레이 하는 도중 퀘스트들의 상태는 ..

문제 이 문제를 풀기 위해서는 가장 먼저 다음과 같은 관찰을 해야된다 :가로등을 위치 순서대로 나타내면 가로등의 상태는 항상 켜짐, 켜짐, ... , 켜짐, 꺼짐, ... , 꺼짐, 켜짐, ... , 켜짐 형태이다. 그 다음으로 해볼수 있는 시도는 $\text{dp}[i][j]$를 i ~ j 번 가로등들에 대한 문제의 답으로 정의하고 점화식을 만드는 것이다. 하지만 이렇게 하면 점화식이 잘 만들어지지 않는다. 그 다음으로 시도해볼수 있는 것은 $\text{dp}[i][j]$를 1 ~ i, j ~ N 번 가로등을에 대한 문제의 답으로 정의하는 것이다. 실제로 이렇게 정의하면 점화식을 어렵지 않게 만들 수 있다. (다만 디테일한 부분이 구현을 어렵게 한다.) 끝