목록덱 dp (2)
블로그 옮겼습니다
Codeforces Round #219 (Div. 2) E. Watching Fireworks is Fun
문제 링크 n, m, d (1 ≤ n ≤ 150000; 1 ≤ m ≤ 300; 1 ≤ d ≤ n).수직선에 1, 2, ..., n 의 장소가 있다. m 개의 폭죽이 임의의 시간과 장소에서 발사된다.주인공은 1초에 d만큼 이동할 수 있다. 시작 위치는 아무데서나 시작해도 된다.i번 폭죽이 발사될 때 주인공이 x 지점에 있을 때 얻게되는 행복은 \(b_i - |a_i - x|\) 이다.이 때 모든 폭죽이 발사되고 난 후에 주인공이 얻은 행복의 양이 최대가 되도록 하고싶다.그 아랫줄부터는 m개의 폭죽의 대한 정보 ai, bi, ti 가 주어진다.ai, bi, ti (1 ≤ ai ≤ n; 1 ≤ bi ≤ 109; 1 ≤ ti ≤ 109) dp[i][j] : t_i 시간에 j 위치에 있을 때 최대 행복도\(dp[..
Algorithm/Problem Solving
2017. 8. 10. 18:51
BOJ 5977번 Mowing the Lawn
문제 링크 N
Algorithm/Problem Solving
2017. 8. 7. 16:07