[일반] scpc B번 어떤 관찰이 필요한거임?

[익명(118.235)]

n^3 dp로 섭테는 긁고 나서 한 항을 O(1)만에 계산하게 최적화할 수 있나 계속 머리 굴려봤는데 못찾겠더라 ㅠ

그리디한 뭔가가 성립할 수 있는건가? 아님 애초에 dp 문제가 아닌건가?

힌트 좀...

[익명(221.148)]

i번부터 j번까지의 값이 (i, j - 1), (i + 1, j)와 대부분의 경우 같음

[익명(221.148)]

i번부터 j번까지는 { a_i, ... a_j }에서 얻을 수 있는 최댓값을 의미

[익명(61.253)]

그럼 어떤 경우에 안같음?

[biigbang(223.38)]

left와 right 둘로 나눠 생각하는데 left는 (a, b)보다 (a - 1, b)가 유리하고 right는 (a, b) 보다 (a + 1, b)가 유리해. 그래서 left인 경우 (a, b)에서 (b, b)에 대해 감소하는 함수이고 right는 증가하는 함수. 그래서 left와 right가 cross하는 근처가 최소값. 그 근처에서 계속 값을 찾으면

[biigbang(223.38)]

(a + 1, b)가 아니라 (a, b + 1)