本番このDPは思い浮かばなかったな。 http://codeforces.com/contest/512/problem/D

状態が膨らむ無駄解法を繰り返して手間取った。 http://yukicoder.me/problems/125