[AOJ] No. 0611 シルクロード (Silk Road)

2019年11月11日

問題

方針

都市 \( i \ (1 \leq i \leq N)\) に到達して滞在する可能性のある日 \( j \) の範囲は、\( i \leq j \leq M – N + i\) となります。ここで、次の配列を考えます。\( d(i, j) \) を \( j \) 日に都市 \( i \) に到達したときの疲労度の最小値とします。この配列の更新は、

\[d(i + 1, j + 1) = \min(d(i + 1, j + 1), D_iC_j + \min \{ d(i, j), j = i, i + 1, \cdots , M – N + i\})\]

となります。答えは、\( \min \{ d(N, i), i = N, N + 1, \cdots, M\} \) となります。

コード