Ecasdqina's MEMO

Ecasdqina's MEMO.

メモ帳.

2017JOI予 - D 水ようかん の思考メモ

こんな感じで考えた〜ってやつです。

メモ本文

最小値・最大値の二値が必要
どちらかを添字にすればよい
最大値 を添字にする、すると最小値の最大値を持てばよいことが分かる
添字を考える DP[i][j] := i番目までで最大値jの時の最小値の最大値
遷移を考える、切った場合と切らない場合
切った時に一番右側の長さを持てないと気づく
これも添字にすればよい、再び考える
DP[i][j][k] := i番目までで最後にjで切ったときの最小値の最大値
遷移を考える
書く
提出
MLE
添字iは2値で十分
提出
AC

Submission

Submission #3107871 - JOI2017/2018 予選ページ