microbeのブログ

進捗ダメです

POJ1036 : Gangsters

1036 -- Gangsters

動的計画法の練習

 

問題概要

時間Tiに価値Piのギャングiがレストランにきて,レストランのドアの状態がSiであればレストランに入る.
レストランのドアは1単位時間ごとに状態を1上げるか下げる,もしくはそのままにすることができるので,レストランに入ったギャングの価値を最大化する.

(英語が絶望的に出来ないので正しい翻訳ではなく自己解釈です.悲しいね.)

 

方針

最初に書いちゃってるけど動的計画法

あらかじめ時間でソートしておく.
dp[i] : =i人目を見たときの最大値
Ti,Tjの差<Si,Sjの差の絶対値 の場合は入れることが不可能なので除外.

 

ソース

gistdc32dcf8dba7c8f44e66bb2f89a4f57d

 

英語が読めないというのもあるんだけどPOJの問題なんか苦手だなあ
JOI非公式難易度表を優先的に埋めようと思います.