AOJ 2233 - Carrot Tour - ツバサの備忘録

解法

これ自力で解ききれなかったの悔しいですね…
dp[i][j][k] = k回目の移動でiからjに移動するときの、それまでの移動距離の合計の最小値
とします。こうすることで、持っているにんじんの個数は自動的にkになります。
そして、
dis[i][j] = 都市iとjの距離
とすると、
dp[i][j][k] = min(dp[x][j][k-1] + dis[i][j])
となります。
ただし、これは都市x->i->jの順に進むことができる場合、です(つまり、都市iで方向転換したときに問題の条件を満たすときです)。
これをx,i,j,kについて全探索していき、あるkについてdp[i][j][k]が更新されなくなった時点で、答えがk-1となります。
あとは、方向転換できるかどうかを調べます。
これは、都市x,i,jで三角形を作成し、角xijを計算します。余弦定理と、arccosを使用しました。
その後、180から角xijを引いたものがθ以下になっていれば、方向転換が可能です。方向転換する角度は、内角そのものではないことに気を付けましょう(これに自分はひっかかりました)。
ということで、これが $O(N^{3})$ で前計算でき、dpが $O(N^{3}r)$ となるので時間内に答えを求めることができます。