差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:contest_history:atcoder:2018:0825_arc101 [2020/03/16] – [解法] ikatakosprogramming_algorithm:contest_history:atcoder:2018:0825_arc101 [2020/03/16] – [解法] ikatakos
行 315: 行 315:
 これを踏まえて、以下のDPを考える。 これを踏まえて、以下のDPを考える。
  
-  * $DP[i][j]=$ 左出口までの距離が $i$ であるロボットまでを見て、最後に左に1つ進めるまでの右に進んだ最大距離が $j$ だった時の、出口の組+  * $DP[i][j]= (i-1,j)$ までの経路
   * $DP[0][0] = 1$   * $DP[0][0] = 1$
 +
 +これは何を示すかというと、
 +
 +  * 左出口までの距離が $i$ 以下のロボットだけを考える
 +  * 座標 $i$ のロボットに関して、右出口までの距離が $j$ 未満のロボットを左、$j$ 以上を右から出している
 +  * $i-1$ 以前のロボットは、通った経路によって左も右もあり得るが、それらを踏まえた出口の組の個数を示す
  
 ただし $j$ については、必要無いのに無駄に右に進むことはせず、 ただし $j$ については、必要無いのに無駄に右に進むことはせず、
programming_algorithm/contest_history/atcoder/2018/0825_arc101.txt · 最終更新: 2020/03/18 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0