[LOJ6039] [아례훈련 2017 Day5] 보석(DP, 의사결정 단조성)

N N 개의 보석이 있는데 각 보석의 가치는 Ci C i이다. Vi V i의 즐거움이 생길 수 있다. 지금 당신은 M M원이 있는데 가장 많은 즐거움을 얻을 수 있느냐고 묻는다. M ∈[1,K] M ∈[1,K]에 대해 질문에 대답한다.N≤106,K≤104,Ci≤300 N ≤ 10 6 , K ≤ 10 4 , C i ≤ 300 먼저 Ci Ci가 비교적 작다는 것을 알 수 있다. 우리는 Ci Ci...

LOJ예절에 맞는 훈련 훈련.DP정책 결정의 단조성

BZOJ P4033 LOJ 2124 [HAOI 2015] 나무 염색[나무형 DP+가방]

우리는 X X를 뿌리로 하는 자수 밖(X X 점 포함)에 모두 PP의 검은 점이 없다고 가정하면 X X를 뿌리로 하는 자수 안, 즉 YY 안(X X 점 포함하지 않고 Y 점 포함)에 모두 M-P M - P의 검은 점이 있다.관건은 곱셈 원리에 따라 모든 검은 점이 가장자리에 연결되면 모두 P (M: P) P (M: P) 테두리가 있는데, 이 P (K: P) P (K. P) 테두리는 모두 같은...

LOJ동적 계획 - 트리 DP동적 계획 - 백팩 DPBZOJ동적 기획과 추이