#5484 정원

https://www.acmicpc.net/problem/5484

문제설명은 힌트로 대체한다.
우리는 겹치지 않는 두개의 직사각형을 골라야 한다. 각각의 직사각형 내부에, 장미가 k개 있으면 된다!

요즘 ps에 대한 자신감이 하락하고 있었는데, 어떻게 갑자기 플레1을 내힘으로 풀었다!
어려운 문제 푸는게 확실히 구현력, 사고력에 도움이 되는듯.

정해는 모르겠는데 나는 $O(logN*N^2)$에 해결했다.

어떻게 풀까?

 

prefixsum+binary_search+dp로 해결 가능하다.

 

 

우리가 1번 직사각형을 선택한다고 해보자. 그럼 전체 꽃밭에 있어서, 1,2,3,4,5로 나누어진다. (각각 겹치는 부분이 있다.)

1. 2차원 prefix_sum으로 우리가 원하는 범위에 꽃이 몇개있는지를 O(1)에 가져오자

2. 이를 이용하고, 꽃의 수는 가로위치가 정해졌을때 높이에 따라 단조증가함을 이용하면 binary search를 할 수 있다. (둘레의 최소값을 구해야 하므로)

3.그럼 dp 2가지를 정의하자

    1.현재 위치에서 오른쪽 위의 부분을 전부볼때 존재하는 최소 직사각형 

    2.현재 위치에서 왼쪽 아래 부분을 전부 볼때 존재하는 최소 직사각형

 

4.dp를 채우는 식은 복잡해서 쓰진 않겠지만 여기서도 binary search가 쓰이고, dp를 참조함을 이용하면 자연스레 $O(logN*N^2)$ 에 가능하다.

 

5.직사각형 하나를 고르면 2번 5번 영역에는 1번 dp를 3,4번 영역에는 2번 dp 를 이용해서 둘 중 비교하여 최소값을 1번 둘레에 더하면, 1번 직사각형을 골랐을때 최소 둘레이다. 

6. 이를 이용하여 $O(logN*N^2)$에 해결가능하다.

 

어렵다!