POJ No. 1769 Minimizing maximizer
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の8日目のエントリです．
問題要約
- 数値をソートすることによって最大値を出力するMaximizerがある
- Maximizerはk個のsorterから構成されている
- sorter i は[latex]s_i[/latex]から[latex]t_i[/latex]までの値をソートする
- 取り除いても問題の無いsorterを取り除き必要なsorterの最小数を求める
解法
- sorterのカバーする範囲をちょっとずつ被せて全体がカバーできればよい
- 動的計画法とセグメントツリー(Range Minimum Query)を組み合わせる
- dp用の配列をdp[1]=0で初期化
- 1つ目のsorterから順に
dp[[latex]t_i[/latex]]=min(dp[[latex]t_i[/latex]],dp[[latex]s_i[/latex]]からdp[[latex]t_i[/latex]]の最小値)
とすして求める． - 最後のsorterまで確認し終わったらdp[n]が答え
どうでもいいけど，cin使ったらTLEした．
