Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

2012-09-24から1日間の記事一覧

AOJ 2431 - House Moving

問題文 : 引越し解法 : 荷物を動かすために使う体力を最小化する、ということは 動かさない荷物の重量を最大化する、ということと等しい. ゆえに, 増加する部分列のうち, 重さが最大のものを総重量から引いたものが答えとなる.荷物の重さをkとし, dp[k] -> …

PKU 3171 - Cleaning Shifts

問題文 : Cleaning Shifts解法 : dp[Ei] -> Ei秒まで掃除するのに必要な時間, とし, 牛iが時間Si秒からEi秒まで掃除でき, 雇うのに給料がMiかかるとすると dp[Ei] = min(dp[Ei], min(dp[Si] ~ dp[Ei]) + Mi) となる. dpテーブルはINFなどで初期化しておく. …