[일반] D 어케풂???

[익명(1.236)]

감이안잡히네 세그인지 dp인지도

[EN_SA(encludingsalt)]

이분탐색에 세그로 최적화한 dp

[익명(1.236)]

세그로 최적화 어케시키는지 알수 있을까

[EN_SA(encludingsalt)]

일단 답을 x로 고정하고, dp[i] := block되지 않은 segment의 합이 x를 넘어가지 않게 하면서 i번째 요소를 마지막으로 block 했을때 a[1..i]의 cost라고 정의하자

[EN_SA(encludingsalt)]

그럼 dp[i] = min{ dp[j] + a_i } (단, j < i이고, a[j+1..i-1]의 합이 x보다 작거나 같음)

[EN_SA(encludingsalt)]

투포인터나 이분탐색등을 활용하면 각 i마다 j를 어디서부터 봐주어야하는지는 쉽게 알 수 있고, 이미 계산된 dp 값을 최솟값 세그트리에 박아넣으면 dp 식을 log안에 계산할 수 있다

[EN_SA(encludingsalt)]

이제 여기서 dp[i] <= x이고 a[i+1..n]의 합 역시 x보다 작다면 아무튼 cost가 x 이하가 되도록 block할 수 있다는 의미가 되고

[EN_SA(encludingsalt)]

이 x를 이분탐색하면 됨

[EN_SA(encludingsalt)]

아 dp 정의 살짝 잘못썼는데 a[1..i]에서 block된 요소들 합의 최솟값임

[익명(1.236)]

와 이런 발상은 어케하는거지..

[EN_SA(encludingsalt)]

부분부분은 국밥처럼 나오는 소재인데 이걸 다 스까버린...

[익명(amamamamam)]

https://www.acmicpc.net/problem/11003
요
문제 아이디어 쓰면 DP계산 선형으로도 됨

[익명(211.234)]

이분탐색하고, 투포인터 느낌으로 구간 관리하면서 dp값 갱신