SRM383 Div2 500

問題

あまった木材を売る。しかし、売る為にはすべて同じ長さの木材でなければ買い取ってもらえない。
もし木を切る場合、カット1回あたりcostPerCutかかる。もし、木材を売る場合、長さLの木材K枚をK*L*woodValueで買い取ってもらえる。
各木材の長さとカットのコスト、単位長さあたりの木材の値段が与えられるので、得ることのできる最大の利益を返す。

考え方

全探索。
カットする長さについて1から10000までループを回す。
その長さiが決まれば、各木材は「そのまま捨てる」か「カットする」かを独立に決められる。
捨てる場合とは、カットするコストが高く、売る値段よりもカットした値段の方が高くなってしまうような時。
各木材についてその長さでの最大の利益を求め、すべての長さで最大の利益を返す。

反省

切る切らないの組み合わせをすべて試すような考えしか出てこなかった(2^50通り)。
普通に無理なのだから、各木材についてgreedyに求められないかを考えるべき。