競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2333 僕の友達は小さい

問題文がなかなかキチってて好き

解法

ナップサックで解けそうな気がしてくるので,DPで考えてみます.
すると,W-(選んだ友人の高さの合計)が選んでない人の高さの最小値未満なら条件を満たすことが分かると思います.

そのため,dp(選んだ友人の高さの合計,今まで選んでない人の高さの最小値)=(組み合わせ)というDPを更新すればよさそうです・
選んでない人の高さの最小値はあらかじめ友人を高さでソートしておくと楽になると思います.
また,選んでない人の高さは値ではなくindexで持っておかないとTLEしてしまうので注意が必要です.

計算量はO(N^2W)