凸多角形の構成問題とサボテングラフ上の期待値計算、幾何DPの最適化
凸多角形の構成と桁DP：ベクトル選択の数え上げ
凸多角形を構成する際、同一のベクトルは連続して現れる必要があります。この問題は、与えられた $n$ 個のベクトル $(x_i, y_i)$ をそれぞれ $c_i$ 個選択し、閉路を形成しつつ、全ての座標が指定された範囲 $m$ に収まる組み合わせを求める問題に帰着できます。
条件は、正の方向の総和と負の方向の総和が等しく、かつその ...
8月16日 03:46 投稿