[백준] 13262 수열의 OR 점수

Divide and conqure optimization 문제가 예전 글들 안찾아보고도 슥슥 구현이 되는걸보니 이제 좀 손에 익은것 같다. 이 문제는 O(N^2)에 DnC Opt 를 돌려야 하는데, 일단 DnC 가 동작하는 이유를 알아보자. 이 그 뭐시기냐 점화식이고 구간합 OR 배열은 당연히 Monge array가 아니다. 하지만 opt[k][i]와 opt[k][i+1]을 비교해보자. OR 연산이므로 수가 더 추가되면 최적해를 앞으로 갈 이유가 없다. 무조건 그자리거나 뒤로가는게 최적이기 때문에 최적해의 단조성이 보여져서 DnC opt를 쓸 수 있다. 시간제한이 빡빡해보여서 OR을 처리하기 위해 O(30) 짜리 구간합 배열이나 세그먼트 트리를 안쓰고 sparse table로 O(1) 쿼리가 가능하도록 전..........

원문링크 : [백준] 13262 수열의 OR 점수