AOJ 2965 - F グリッドの番号

問題
提出コード

解法

小さい順に数字を当てはめていくとき、上段の右端に配置するか、下段の右端に配置するかの二択になることを利用します。
番目までの数字を入れ終えて、上段に配置した個数が個かつ、直近手の上下の配置情報がのときの配置の通り数
とします。
配るDPを考えると、
を配る箇所は、を上段の左から番目に配置した場合と、下段の番目に配置した場合の2か所です。
それぞれのパターンについて、配置したときに矛盾がないかを確認し、問題が無ければ値を配れば良いです。
矛盾がないかを確認するには、をもとに状態を復元します。
上段に配置する場合は、上段の番目の数をチェックしてとの差が以下か、
下段に配置する場合は、上段の番目の数と下段の番目の数をチェックして、との差が以下かチェックすればよいです。