$dp[i][j]:=$ $i$ 章が $j$ ページ目で終わるときの繋がりの最大値
$chmax(dp[i+1][r+1], dp[i][l] + cnt[l][r])$
- ただし、 $cnt[l][r]$ は $l$ ページ目から $r$ ページ目までを一つの章としたときの繋がりの個数
$i$ 章を $l$ ページ目から $r$ ページ目までとするような3重ループを回してDP配列を更新する

$P=0$ かどうかで場合分け。

$P=0$ の場合
- $A_i=0$ なら、答えに $i$ を加算。（0-indexed）
- $A_i \ne 0$ なら、これまでに現れた $A_i=0$ の個数を答えに加算
$P \ne 0$ の場合
- 以下のように式変形をする
- $A_iA_j%M=P$ ( $M$ は1000000007 )
- $A_iA_j=Mk+P$ ( $k$ は整数 )
- $A_j=A_i^{-1}Mk+A_j^{-1}P$
- $A_j≡A_i^{-1}P$ ( mod $M$ )
- よって、mapでこれまでに現れたら $A_j$ の個数をカウントして、 $A_i^{-1}P$ と一致するものの個数を答えに加算すればよい

始点からのダイクストラと、終点からのダイクストラをそれぞれ行う。

頂点 $i$ が最短経路に含まれるかどうかは、始点から頂点 $i$ までの最短距離と、終点から頂点 $i$ までの最短距離の合計が始点から終点までの最短距離と一致しているとき。

【★解説AC★】

左から区間スケジューリングした結果と、右から区間スケジューリングした結果を前処理しておく。各会議 $i$ について、以下が答え。 $L_i$ までに会議が終了しているときの最大 + 1（会議 $i$ の分）+ $R_i$ 以降に始まる会議の最大

【★解説AC★】

重実装すぎた問題。始点、各空港の頂点、フライト前と後の頂点、各空港の頂点、終点を用意して、 $1+N+2M+N+1$ 頂点のグラフを作成してDPをする。

DP値は時刻の昇順に更新していく。そのため、フライト前と後の頂点は時刻の昇順に頂点番号をつけておくと、頂点番号順にDP値を更新していけばいいので実装が楽になる。というより、BFSやトポソ順だとうまくいかなかったので、その順番にする必要がある。

【★解説AC★】

Dequeを2つ使用する。列の真ん中から分けて、前半分と後ろ半分をそれぞれ管理する。

データ構造系の問題は $2$ つ（以上）組み合わせてうまくいかないかを考えるとよさそう。

区間DPをする。

$dp[l][r]:=$ 区間 $[l, r]$ でかかるコストの総和の最小値
$chmin(dp[l][r], dp[l][i] + dp[i + 1][r])$ $(l + 1 \le i \le r - 2, i$ は $2$ ずつ進める $)$
- 左右で分割して遷移
$chmin(dp[l][r], abs(a[l] - a[r]) + dp[l + 1][r - 1])$
- 両端と真ん中で分割して遷移

【★解説AC★】

セグ木を使う。ふわっとした理解しかしていない。

まず、給油するガソリンの総量は $L-K$ リットル。 $i$ リットル目のガソリンを得るための最小価格は、区間 $[i+1, i+k]$ にあるガソリンスタンドの最小価格になるので、これをセグ木で高速に求める。

ヒューリスティックなので飛ばします＞＜

競技プログラミングの鉄則 演習問題集（力試し問題） - noko206/AtCoder GitHub Wiki

競技プログラミングの鉄則 演習問題集（力試し問題）