2014-08-08から1日間の記事一覧

POJ 2010: Moo University - Financial Aid

概要 コストa[i]と評価値s[i]の組の列がある. この中から,N(奇数)個の要素をコストの合計がFを超えないように選び,メディアンを最大化したい. 解法 メディアンはソートしたときの中央値であり,中央の値以外には影響をうけないことを利用する. N = 2K…

POJ2184: Cow Exhibtion

概要 100個以下の要素からなる(S[i],F[i])の列がある.(-1000 この列からいくつかの要素を選び,S[i],F[i]の総和をとる. S[i]の総和とF[i]の総和が0を下回らないという条件のもとで,S[i]とF[i]の総和を最大にする. 解法 S[i]について降順にソート. dp[i…