yukicoder No.679 不思議マーケット
個の必ず買わせることができる商品を先に買わせ, 条件を満たしているものから貪欲に買わせることで最大値を得ることができます. 条件を満たしている商品は, 買う順番が少し後になっても条件を満たしたままであることがポイントです. 計算量はになりました.
解説をみるとグラフの強連結成分が〜とか書いてあってそのへんがわかるともっと速いコードが書けるっぽいです.
個の必ず買わせることができる商品を先に買わせ, 条件を満たしているものから貪欲に買わせることで最大値を得ることができます. 条件を満たしている商品は, 買う順番が少し後になっても条件を満たしたままであることがポイントです. 計算量はになりました.
解説をみるとグラフの強連結成分が〜とか書いてあってそのへんがわかるともっと速いコードが書けるっぽいです.