keyword 動的計画法 C++ 概要 長さn(自然数である。いくつかの要素を取り除いて全ての要素が連続する様にしたいとき(111332444など)、最小でいくつ取り除く必要があるか求める問題。 kが小さいのでビットDPが思い浮かぶ。dp[n][既に置かれている要素][直前の…

keyword 動的計画法 C++ 概要 100*100以下のボードがあり、各セルに高さが設定される。自分のセルより低い4近傍に移動できるとき、最も長いルートの長さを求める問題。 4近傍で極小(or 極大)の高さのセルから開始すれば素直なDP。 今考えると適当な点から幅…

keyword 平面幾何 反射 C++ 概要 ビリヤード台の幅と高さが与えられる(穴は無い)。中心からショットして、s秒後に縦横の壁にそれぞれm,n回衝突して中心に戻ってくる(衝突は全て弾性衝突)。このときのショットの角度と速度を求める問題。 セオリー通り反射は…