목록행렬 dp (1)
블로그 옮겼습니다
Codeforces Round #420 (Div. 2) E. Okabe and El Psy Kongroo
http://codeforces.com/contest/821/problem/E (0,0) 에서 (k,0) 까지 가는 방법의 수를 구하는 문제이다.이동을 할 때에는 세가지 방법이 가능하다. (x,y) 에서 (x+1,y-1), (x+1,y), (x+1, y+1) 이렇게 세가지 이동이 가능하다.대신 n개의 선분이 주어진다. 구간은 ai, bi, ci 로 표현되며y좌표가 ci 이면서 x좌표가 [ai,bi] 인 선분이다. 출발지에서 도착지까지 갈 때이 선분을 넘어가면 안된다. bi=ai+1 라는 조건과 an≤k≤bn 라는 조건이 주어진다.그리고 ci 는 최대 15이며 ai,bi,k 는 10^18 이하이다. 뻔한 행렬 dp 이다. 12345678910111213141..
Algorithm/Problem Solving
2017. 6. 28. 19:17