[질문] CHT 식 관련 질문

[익명(61.74)]

점화식이 DP[i]=max(DP[j]+A_i*A_j+B_j)+B_i 꼴이면 CHT 쓸 수 있다고 알고 있습니다.

그런데 사람마다 어떤 사람은 DP[j]를 살려서 직선의 상수항에 B_j만 넣고

또 어떤 사람은 DP[j]+B_j를 넣더군요...

보통 어느 방식이 더 일반적인가요? 

지저분한 전처리를 안하는 방법을 되도록 쓰고 싶습니다.

[익명(125.131)]

두번째걸 써야하지 않나요? 잘모르겠네요 - dc App

[익명(61.253)]

DP를 안살리고 dp를 구할수가 있음? cht 이해를 잘 몬한거같은데

[익명(61.74)]

어차피 항상 DP값이 상수 부분에 들어가니까 직선 넣을 때 한번에 넣고 하는 경우도 있더라구요

[무구정광대다라니경(woaldudrl)]

생각하기 귀찮으니 j만 넣자