이동식 저장소

2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d≤10,000이고, 1≤N≤1,000,000이다. www.acmicpc.net 규칙에 따라 변하는 짚신벌레의 상태를 추적하는 문제이다. 딱 봐도 dp스럽지 않은가? 짚신벌레의 상태는 날짜에 의해서만 변하므로, $i$번째 날의 값을 알면 $i+1$번째 날의 값도 알 수 있다. 다음을 정의한다. $t[i][j]$: $i$번째 날에 상태가 $j$로 바뀌는 짚신벌레의 수 $sum[i][j]$: $i$번째 날에 상태가 $j$인 짚신벌레의 수 ($t$의 부분합이라고 생각하면 좋다) 상태 $j$는 다음과 같다. $j=0$: 태어남 (태어났지만 성체는 아님) $j=1$: 성체가 ..