Aliens (IOI 2016) の解法はラグランジュ緩和 + CHT です。
ラグランジュ緩和の部分を指して Alien DP と呼ぶことがあります。この部分の別名が WQS binary search です。この指し方だともはや DP すら使わないこともあります。
CHT の部分を更に強いアルゴリズム (LARSCH など) に変えることで辺重みが Monge のグラフの d-edge shortest path を求めるアルゴリズムに一般化できます [1]。
Alien DP は俗称である上に人によって指すものが違うため、何を書くか決めかねています。d-edge shortest path for Monge graph などと銘打って書いてしまうということも考えていますが、どうでしょうか？
[1] Bein, W. W., Larmore, L. L., & Park, J. K. (1992). The d-edge shortest-path problem for a Monge graph (No. SAND-92-1724C; CONF-930194-1). Sandia National Labs., Albuquerque, NM (United States).
Aliens (IOI 2016) の解法はラグランジュ緩和 + CHT です。
ラグランジュ緩和の部分を指して Alien DP と呼ぶことがあります。この部分の別名が WQS binary search です。この指し方だともはや DP すら使わないこともあります。
CHT の部分を更に強いアルゴリズム (LARSCH など) に変えることで辺重みが Monge のグラフの d-edge shortest path を求めるアルゴリズムに一般化できます [1]。
Alien DP は俗称である上に人によって指すものが違うため、何を書くか決めかねています。d-edge shortest path for Monge graph などと銘打って書いてしまうということも考えていますが、どうでしょうか？
[1] Bein, W. W., Larmore, L. L., & Park, J. K. (1992). The d-edge shortest-path problem for a Monge graph (No. SAND-92-1724C; CONF-930194-1). Sandia National Labs., Albuquerque, NM (United States).