問題リンク 解説 まず、$P$ 頂点のグラフを構築できれば、その中での経路のうち辺のコストの最大値の最小化をすればいいことになる。 このグラフ上でクラスカル法みたいなことをやれば、木上の問題になるのもすぐわかる。 さて、この木の構築方法だが、各建…

問題リンク 解説 bit DP くらいしか解けそうな方法がなくて困るが、制約を眺めると $D_i\leq 7$ になっている。つまり、一定以上に離れた位置にある小籠包を食べる順番は美味しさの総和に関係ない。 次のような DP をする。 $dp[i][j]=i$ 番目の小籠包を食べ…