はまやんはまやんはまやん

hamayanhamayan's blog

2017-05-31から1日間の記事一覧

競技プログラミングにおける線形計画問題・整数計画問題まとめ

線形計画問題 LP : Linear Programming シンプレックス法という解法があるが、これを使うのはまれ 双体というのを取ると、フロー問題に帰着できる場合がある 参考1 参考2 整数計画問題 IP : Integer Programming これを解くのは難しい 枝刈りを上手くやる全…

MaximumRange [SRM 715 Div1 Easy]

問題概要 "+"と"-"から成る文字列がある。 "+"は数をインクリメントする命令で、-は数をデクリメントする命令。 ここから、連続でなくてもよい部分文字列をとって、X=0に対して実行する時、Xの範囲(=Xの最大-Xの最小)を最大化せよ