No.496

クリスタルを使う順序は関係ないので, クリスタルを使う/使わないだけ分かればいい.

$i$ 番目のクリスタルまで見たときに $(x, y)$ に居るときの最小コストを $A(i, x, y)$ とすると,

$$A(i, x, y) = \min(A(i, x, y), A(i-1, x-x_i, y-y_i) + c_i)$$

となる.

ただし, $A(0, x, y) = F(x+y)$ である.

これを DP で計算して $A(N, G_x, G_y)$ が答えとなる.